/<> 백준 20303번 : 할로윈의 양아치 (C언어)

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

 

 

유니온 파인드(Union-Find)와 다이내믹 프로그래밍(DP)을 이용하는 것이 큰 틀입니다. 처음에 DP를 사용하지 않고 문제를 풀어갔는데, 친구 그룹이 꼭 하나란 보장이 없기에 DP를 사용해야 되는 것을 깨달았습니다.. (ex. K = 8, 각각 3명, 4명씩 친구인 그룹의 총 사탕 합이 최대일 수 있음)

 

1. 아이들이 가지는 사탕 개수 배열, 유니온 파인드의 부모 배열, 루트를 중심으로 그룹에 속한 아이들의 수를 저장하는 사이즈 배열, 최대 사탕 수를 저장하는 dp 배열을 생성합니다.

 

2. 친구 관계를 입력받을 때마다 유니온 파인드를 통해 아이들의 관계를 정리합니다. 이때 하위 그룹을 귀속할 때 상위 그룹의 루트에 하위 그룹의 사이즈, 총 사탕 수를 더해줍니다. 루트를 기준으로 총 명 수와 사탕 수를 저장하면 dp 계산이 편해집니다.

 

3. 그룹의 루트인 애들만 기준으로 dp 배열을 채웁니다. 그리고 반복문을 통해 다른 그룹과 사탕을 합칠 수 있으면 새로 업데이트합니다.

 

4. 계산이 끝난 dp 배열의 원소들 중 최댓값이 구할 수 있는 최대 사탕 수입니다.

 

 

<코드>

#include <stdio.h>

int n, m, k;
int candy[30001];
int parent[30001];
int size[30001];
int dp[3001] = {0,};

int find(int x) {
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void union_set(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if(rootA != rootB) {
        parent[rootB] = rootA;
        size[rootA] += size[rootB];
        candy[rootA] += candy[rootB];
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &k);

    for(int i = 1; i <= n; i++) {
    	parent[i] = i;
        size[i] = 1;
        scanf("%d", &candy[i]);
    }

    for(int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        union_set(u, v);
    }

    for(int i = 1; i <= n; i++) {
        if(find(i) == i) {  // 그룹의 루트인 경우에만 계산
            for(int j = k - 1; j >= size[i]; j--) {
                if(dp[j] < dp[j - size[i]] + candy[i]) {
                    dp[j] = dp[j - size[i]] + candy[i];
                }
            }
        }
    }

    int max = 0;
    for(int i = 0; i < k; i++) if(dp[i] > max) max = dp[i];

    printf("%d\n", max);
    return 0;
}

 

 

1. 친구 관계를 입력할 때 바로 유니온 파인드 진행

2. 루트 아이에게 그룹의 사이즈와 총 사탕 수 저장

 

이 두 가지를 생각하지 못해 애를 먹었습니다. 특히 두 번째, 즉 루트들 간의 연산의 편리성을 깊게 느꼈습니다.