BOJ 20303번: 할로윈의 양아치

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

20303번: 할로윈의 양아치

그래프 탐색과 배낭 문제를 섞어놓은 문제였다.

1. 일단 주어진 그래프를 DFS로 탐색하여 배열에 [원소의 개수(우는 아이들의 수), 총 캔디 개수] 를 추가하였고

2. 이 배열을 가지고 dp를 활용하여 배낭 문제를 푸는 방식으로 풀었다.

dp[i][j] = j 명의 아이들이 울면 어른들이 들킬 때 i번째 배열의 수까지 탐색했을 때 최대 캔디수

그리고 다른 배낭 문제와 다르게 K명이 울면 들키기 때문에 dp에 넣을 수 있는 경우는 우는 아이들의 수 < j 일때이다.

 

파이썬은 시간초과가 났고 pypy로 통과했는데 통과한 사람들 언어를 보니 python이 없는 걸로 봐서는 python으로는 통과하지 못하는 문제인 것 같다.

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
candy = list(map(int, input().split()))
friends = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)
visit = [False]*(N+1)
arr = []
arr.append([0,0])
def dfs(v):
    st = [v]
    visit[v] = True
    cnt = 0
    c = 0
    while (st):
       now = st.pop()
       cnt += 1
       c += candy[now-1]
       for i in friends[now]:
           if (visit[i]==False):
               visit[i] = True
               st.append(i)
    arr.append([cnt, c])
cnt = 0
for i in range(1, N+1):
    if (visit[i]==False):
        dfs(i)
        cnt += 1


dp = [[0]*(K+1) for _ in range(cnt+1)]
for i in range(1, cnt+1):
    for j in range(1, K+1):
        if (arr[i][0] < j):
            dp[i][j] = max(dp[i-1][j-arr[i][0]]+arr[i][1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[cnt][K])