[할로윈의 양아치/G3/Pypy3]

20303번 할로윈의 양아치 G3

 

문제
10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다. 단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 K명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.\

입력
첫째 줄에 정수 N, M, K가 주어진다. N은 거리에 있는 아이들의 수, M은 아이들의 친구 관계 수, K는 울음소리가 공명하기 위한 최소 아이의 수이다. (1≤N≤30,000, 0≤M≤100,000  1≤K≤min {N,3 000})
둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 c1,c2,⋯,c_n이 주어진다. (1≤ci≤10 000)
셋째 줄부터 M개 줄에 갈쳐 각각의 줄에 정수 a, b가 주어진다. 이는 a와 b가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. (1≤a, b≤N, a≠b)

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

 

 

다이나믹 프로그래밍, 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합, 배낭 문제

 

문제 해결을 위해 분리 집합과 배낭 문제 알고리즘을 사용했다.

 

각 그룹이 몇 명으로 구성되어 있고, 몇 개의 사탕을 가지고 있는지 분리 집합을 통해 구한다.

인원과 사탕의 정보를 배낭 알고리즘에 적용하여, 뺏을 수 있는 최대 사탕의 개수를 구한다.

 

 

import sys
sys.setrecursionlimit(10**6)


def solution():
    n, m, k = map(int, sys.stdin.readline().split())
    candys = list(map(int, sys.stdin.readline().split()))
    p = list(range(n))
    num = [1] * (n)
    dp = [0] * k
    
    def find(v):
        if v == p[v]:
            return v
        p[v] = find(p[v])
        return p[v]
    
    def union(v1, v2):
        r1, r2 = find(v1), find(v2)
        if r1 == r2:
            return
        p[r1] = r2
        num[r2] += num[r1]
        candys[r2] += candys[r1]
    
    for _ in range(m):
        v1, v2 = map(int, sys.stdin.readline().split())
        union(v1-1, v2-1)
    
    data = []
    for i in range(n):
        r = find(i)
        if candys[r] == 0: continue
        data.append((num[r], candys[r]))
        candys[r] = 0
    
    for n, c in data:
        for w in range(k-1, n-1, -1):
            dp[w] = max(dp[w], dp[w-n]+c)
    
    print(dp[-1])
solution()

 

---

python3으로는 통과를 받지 못해, pypy3으로 제출하여 통과를 받았다.

python3으로 통과한 사람이 0명인 것으로 보아 빡빡하게 책정되어 있는 것 같다.