[백준] 29. 할로윈의 양아치 20303 해설

할로윈의 양아치

20303번: 할로윈의 양아치

문제

나쁜 스브러스가 k-1명 이하의 아이들을 상대로 최대의 사탕개수를 빼앗으면 되는 문제입니다.

다만 아이들은 각각 친구를 가지며 어떤 아이의 사탕을 뺏을 경우 그 아이와 친구관계로 이루어진 모든 아이의 사탕까지 뺏어줘야 됩니다.

풀이

백준 Class 순서에 맞게 문제를 풀어왔기 때문에 해당 문제는 어렵지 않게 풀 수 있었습니다.

 

K-1명 이하의 친구들을 상대로 최대의 사탕개수를 빼앗아주면 된다.

= K kg 배낭에 최대 가치의 물건을 넣는다.

결국에는 배낭 문제와 동일합니다.

 

다만 아이의 사탕을 뺏을 때 해당 아이의 친구관계인 모든 아이까지 사탕을 뺏어야 되기 때문에 관련 있는 아이들끼리 그룹화를 해줘서 진행해 주면 됩니다. 그룹화는 bfs, dfs, union-find 등 상관없이 그룹만 만들어주면 됩니다.

 

 

두 개의 코드가 있지만 두 번째 코드가 더 효율적입니다.

 

첫 번째 코드 bfs + 2차원 배열 DP

그룹화 과정은 bfs를 이용하였고 최대 사탕을 얻는 과정은 기존 배낭문제의 풀이 방식 그대로 이용해 주었습니다.

import java.io.StreamTokenizer
import java.util.LinkedList

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    val N = input() // 아이들 수
    val M = input() // 아이들의 친구 관계 수
    val K = input() // 울음 소리가 공명하기 위한 최소 아이의 수

    val candy = IntArray(N+1)
    for (i in 1..N) candy[i] = input()
    val arr = Array(N+1) { arrayListOf<Int>() }

    // 친구 관계
    repeat(M) {
        val a= input()
        val b= input()
        arr[a].add(b)
        arr[b].add(a)
    }

    // 친구끼리 그룹을 만들어줌 bfs
    data class Group(val count: Int, val sum: Int)  // 인원수, 캔디 합
    val visited = BooleanArray(N+1)
    val group = arrayListOf<Group>()
    for (i in 1..N) {
        if (!visited[i]) {
            var count = 0
            var sum = 0
            val queue = LinkedList<Int>()

            queue.add(i)
            visited[i] = true

            while (queue.isNotEmpty()) {

                val cur = queue.poll()
                count++
                sum += candy[cur]

                for (next in arr[cur]) {
                    if (!visited[next]) {
                        queue.add(next)
                        visited[next] = true
                    }
                }
            }
            group.add(Group(count, sum))
        }
    }

    // 배낭문제와 동일
    val len = group.size
    val dp = Array(K) {IntArray(len)}
    for (i in 0 until K) {
        if (i >= group.get(0).count)
            dp[i][0] = group.get(0).sum
    }

    for (i in 0 until K) {
        for (j in 1 until len) {
            if (group[j].count > i) {
                dp[i][j] = dp[i][j-1]
            } else {
                dp[i][j] = Math.max(dp[i][j-1], dp[i-group[j].count][j-1] + group[j].sum)
            }
        }
    }
    print(dp[K-1][len-1])
}

 

 

두 번째 풀이 union-find + 1차원 배열 DP

그룹화 과정은 union-find을 이용하여 메모리를 더 아낄 수 있었습니다.

최대 사탕을 얻는 과정은 굳이 2차원 배열을 쓰지 않고도 1차원 배열만으로 해결할 수 있었습니다.

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    val N = input() // 아이들 수
    val M = input() // 아이들의 친구 관계 수
    val K = input() // 울음 소리가 공명하기 위한 최소 아이의 수

    val candy = IntArray(N+1)
    for (i in 1..N) candy[i] = input()

    val parents = IntArray(N+1) {it}
    val rank = IntArray(N+1)

    fun find(num : Int): Int {
        if (parents[num] == num)
            return num
        return find(parents[num])
    }
    fun union(n1: Int, n2: Int) {
        val p1 = find(n1)
        val p2 = find(n2)
        if (p1 == p2) return

        if (rank[p1] == rank[p2]) rank[p1]++
        if (rank[p1] > rank[p2]) parents[p2] = p1
        else parents[p1] = p2
    }
    // 친구끼리 그룹화
    repeat(M) {
        val a= input()
        val b= input()
        union(a, b)
    }

    // 그룹의 총 인원수와 총 캔디수를 구해줌
    val sumArr = IntArray(N+1) {candy[it]}
    val countArr = IntArray(N+1) {1}
    for (i in 1..N) {
        val p = find(i)
        if (p == i) continue
        sumArr[p] += candy[i]
        countArr[p]++
    }

    // 배낭문제와 동일하게 k-1명의 인원일 때 최대 캔디수를 구해줌
    val dp = IntArray(N+1)
    for (i in 1..N) {
        if (parents[i] != i) continue

        for (j in K-1 downTo countArr[i]) {
            dp[j] = Math.max(dp[j], dp[j - countArr[i]] + sumArr[i])
        }
    }
    print(dp[K-1])
}