[백준] 20303번 할로윈의 양아치 (C++)

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

 

 

이 문제는 N명의 아이들 수와 M개의 친구 관계 수, K개의 최소 아이수가 주어진다.

이때 사탕을 뺏으려고 하는데 같은 친구관계에 있을때 모든 친구들의 사탕을 뺐는다.

 

이때 K명 미만의 아이들의 사탕을 뺏을때 최대 얻을 수 있는 사탕의 개수를 출력하는 문제이다.

 

 

첫번째 해결해야할 문제는 같은 친구관계에 있을때 얻을 수 있는 사탕의 개수이다.

두번째는 각 친구들이 몇명있는지 알아내야 한다 

 

이는 유니온 파인드 알고리즘 또는 bfs를 사용하여 각 친구 관계와 얻을 수 있는 사탕의 개수를 알 수 있다.

 

두번째 해결해야할 문제는 각 친구 관계와 사탕관계를 나타냈을때 최대한으로 얻을 수 있어야 한다.

처음엔 단순하게 그리디 방식을 사용하여 K미만으로 얻을 수 있는 최대 개수를 구하는 방식을 생각했는데

 

이때 여러개의 반례가 존재할 수 있다는 것을 눈치채지 못했다

따라서 배낭 알고리즘을 사용하여 K미만으로 얻을 수 있는 최대 사탕개수를 구하는 방식을 사용하였다.

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {1, 0};
int dy[] = {0, 1};
int N, M, K;
int arr[30001];
int unf[30001];
halloween graph[30001];
vector<pii> v;
int dp[30001][3000];

int Find(int a) {
    if(a == unf[a]) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a > b) unf[a] = b;
    else unf[b] = a;
}

bool isUnion(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a == b) return true;
    else return false;
}

void Print() {
    for(int i = 1; i <= N; i++) {
        cout << graph[i].cnt << " " << graph[i].score << endl;
    }

    for(auto it : v) {
        cout << it.first << " " << it.second << endl;
    }
}

void solve() {
    for(int i = 1; i <= N; i++) {
        int idx = Find(i);
        graph[idx].cnt++;
        graph[idx].score += arr[i];
    }

    for(int i = 1; i <= N; i++) {
        if(graph[i].cnt > 0) {
            v.push_back({graph[i].cnt, graph[i].score});
        }
    }

    int n = v.size();
    int answer = 0;

    for(int i = 1; i <= n; i++) {
        int weight = v[i-1].first;
        int cost = v[i-1].second;
        for(int j = 1; j < K; j++) {
            dp[i][j] = dp[i-1][j];

            if(j >= weight) {
                dp[i][j] = max(dp[i][j], cost + dp[i-1][j-weight]);
                answer = max(dp[i][j], answer);
            }
        }
    }

    cout << answer << endl;
//
//    for(int i = 1; i <= n; i++) {
//        for(int j = 1; j < K; j++) {
//            cout << dp[i][j] << " ";
//        }
//        cout << endl;
//    }
}

void Init() {
    for(int i = 1; i <= N; i++) {
        unf[i] = i;
    }
}

void input() {
    cin >> N >> M >> K;

    Init();

    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        if(!isUnion(a, b)) {
            Union(a, b);
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

먼저 사용한 변수들을 설명하면

 

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {1, 0};
int dy[] = {0, 1};
int N, M, K;
int arr[30001];
int unf[30001];
halloween graph[30001];
vector<pii> v;
int dp[30001][3000];

 

halloween 구조체 배열은 각각의 아이들의 친구 수와 얻을 수 있는 점수를 나타낸 것이다. 또한 dp 배열은 얻을 수 있는 사탕의 최대 개수를 테이블 형식으로 저장하기 위해 사용하였다.

 

    for(int i = 1; i <= n; i++) {
        int weight = v[i-1].first;
        int cost = v[i-1].second;
        for(int j = 1; j < K; j++) {
            dp[i][j] = dp[i-1][j];

            if(j >= weight) {
                dp[i][j] = max(dp[i][j], cost + dp[i-1][j-weight]);
                answer = max(dp[i][j], answer);
            }
        }
    }

 

가장 핵심 코드인 배낭 알고리즘 코드인다 여기서는 weight 가 나타내는 것은 친구들의 인원 수,

cost가 나타내는 것은 얻을 수 있는 최대 사탕의 개수를 의미한다.

 

이때 j 즉 친구들을 선택할 수 있는 최대 인원을 K 미만까지 잡고 늘려가며 사탕을 얻을 수 있는지 확인하며

만약 담을 수 있다면 이전 값을 가져오거나 이전 친구 개수를 빼서 이번 사탕을 담을 수 있는지 확인하여 최댓값을 갱신하였다.