[백준 / python] 20303: 할로윈의 양아치

https://www.acmicpc.net/problem/20303

문제

Trick or Treat!!

10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 K명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

출력

스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.

풀이

dfs + 배낭 문제

import sys

N, M, K = map(int, sys.stdin.readline().split())
counts = [0] + list(map(int, sys.stdin.readline().strip().split()))
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
max_count = 0
groups = []

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, N + 1):
    if visited[i]:
        continue
    visited[i] = True
    candy = count = 0
    stack = [i]
    while stack:
        current = stack.pop()
        candy += counts[current]
        count += 1
        for node in graph[current]:
            if not visited[node]:
                visited[node] = True
                stack.append(node)
    groups.append((count, candy))

dp = [[0] * K for _ in range(len(groups) + 1)]
for i in range(1, len(groups) + 1):
    count, candy = groups[i-1]
    for j in range(K):
        if j < count:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-count] + candy)

print(dp[-1][-1])