백준 20303번 할로윈의 양아치

🔒[문제 url]

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

🔑알고리즘

하나의 아이 무리를 물건의 무게, 그 무리의 총 사탕 갯수를 물건의 가치로 생각하게 된다면 떠오르는 알고리즘은 knapsack(DP)이다.
즉, 평범한 배낭 문제와 동일해짐을 알 수 있다. 해당 문제 풀이

1. DFS를 통해 친구의 정보를 무리 단위로 설정한다.
2. dp[i]는 $i$명으로부터 훔쳤을 때 사탕의 최대 갯수이고,
각 무리를 순회하며 knapsack을 적용해 dp를 갱신한다.

이때, 평범한 배낭 문제처럼 dp를 2차원 배열로 선언해 해결할 수도 있지만,
공간 복잡도가 매우 커지므로 1차원 배열로 선언한 후, 현재 무리에 의해 갱신되는 dp값에 overlap되지 않도록 $i$를 k-1부터 0까지 감소하며 갱신한다.

아래 사진는dp를 2차원으로 선언한 풀이(위)와 1차원으로 선언한 풀이(아래)의 차이이다.

🐾부분 코드

pair<int,int> setGroup(int x)
{
    int s = 1;
    int c = candy[x];
    visited[x] = true;

    for(int i = 0; i < kid[x].size(); i++)
    {
        if(!visited[kid[x][i]])
        {
            pair<int,int> size_candy = setGroup(kid[x][i]);
            s += size_candy.first;
            c += size_candy.second;
        }
    }
    return {s,c};
}

<DFS 함수 : 무리 설정>
$x$번 아이의 친구들을 묶어 하나의 무리로 설정한다.
무리의 크기 , 총 사탕 갯수를 반환한다.

// 무리 설정
for(int i = 1; i <= n; i++)
{
    if(!visited[i])
    {
        pair<int,int> size_candy = setGroup(i);
        group.push_back(size_candy);
    }
}

<모든 무리 설정>
모든 아이를 순회하며, 무리 단위로 설정한다.

int ans = 0;
dp[0] = 0;
for(pair<int,int> sc : group)
{
    for(int i = k - 1; i >= 0; i--)
    {
        if(i - sc.first >= 0)
        {
            dp[i] = max(dp[i], dp[i - sc.first] + sc.second);
            ans = max(ans,dp[i]);
        }
    }
}

<knapsack 적용>
모든 무리를 순회하며 dp를 갱신한다.
각 무리에 대해 넣는 경우와 안 넣는 경우의 사탕 갯수를 비교해 최댓값으로 갱신한다.

🪄전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,m,k;
vector<int> kid[30001];
vector<pair<int,int>> group;
bool visited[30001];
int candy[30001];
int dp[3001];


void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> candy[i];
    }
}

pair<int,int> setGroup(int x)
{
    int s = 1;
    int c = candy[x];
    visited[x] = true;

    for(int i = 0; i < kid[x].size(); i++)
    {
        if(!visited[kid[x][i]])
        {
            pair<int,int> size_candy = setGroup(kid[x][i]);
            s += size_candy.first;
            c += size_candy.second;
        }
    }
    return {s,c};
}


void SOLVE()
{

    for(int i = 0; i < m; i++)
    {
        int a,b; cin >> a >> b;
        kid[a].push_back(b);
        kid[b].push_back(a);
    }

    // 무리 설정
    for(int i = 1; i <= n; i++)
    {
        if(!visited[i])
        {
            pair<int,int> size_candy = setGroup(i);
            group.push_back(size_candy);
        }
    }

    int ans = 0;
    dp[0] = 0;
    for(pair<int,int> sc : group)
    {
        for(int i = k - 1; i >= 0; i--)
        {
            if(i - sc.first >= 0)
            {
                dp[i] = max(dp[i], dp[i - sc.first] + sc.second);
                ans = max(ans,dp[i]);
            }
        }
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

Union Find가 대표적인 풀이인 듯 하다.
거의 10번의 시도 끝에 겨우 맞힌 문제이지만..!
나만의 풀이를 고집해 성공한 문제였기에 재미있었다.
문제의 아이디어도 기발한 것같다.