할로윈의 양아치(BOJ20303)

문제

이미지 클릭

문제 설명

• n명의 학생이 존재하고 m개의 친구관계가 주어진다.
• 친구 관계를 본다면 특정 사람의 사탕을 뺏는 다면 그 사람의 친구의 사탕도 무조건 뺏어야 한다.
• 만약 사탕을 뺏은 사람의 수가 k를 넘지 않게 해주어야 한다.

문제 해설

• Union-Find

친구의 관계를 나타내기 위해서 특정 친구를 기준으로 하여서 모두 연결해주어야 한다.
예를 들어, 2-4, 4-5 그리고 5-7의 관계가 있다면 친구 7을 기준으로 2,4,5의 대표 친구를 7로 설정해 준다.(bfs로도 가능함..)

• 중간 단계

대표 친구를 기준으로 하여서 친구들의 수와 친구들이 가지고 있는 사탕의 개수를 저장해 준다.

• dp(knapsack)

dp [친구의 수]: 0~k-1명을 체우는 경우의 수를 냅색을 활용하여서 최대를 찾아준다.

최종 코드

#include <bits/stdc++.h>
using namespace std;
long long n, m, k;
vector<long long> parent(30004), d(30004), sum(30004, 0), Size(30004, 0);
vector<long long> dp(30004, 0);
int find(int x) { #find
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}
void unionSets(int x, int y) { #union
    x = find(x), y = find(y);
    if (x != y) parent[y] = x;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        unionSets(x, y); #친구 그룹화하기
    }
    for (int i = 1; i <= n; i++) {
        int p = find(i); #대표 친구(부모)
        sum[p] += d[i]; #사람이 가지는 사탕의 수
        Size[p]+=1; #친구의 수
    }
    for (int i = 1; i <= n; i++) {
        if (Size[i] > 0) {
            for (int j = k - 1; j >= Size[i]; j--) {
                dp[j] = max(dp[j], dp[j - Size[i]] + sum[i]); 
            }
        }
    }
    cout << dp[k - 1]; #k-1명의 최대 사탕개수
}

이미지 클릭