[백준 C++] 20303 할로윈의 양아치 - 다이나믹프로그래밍

 

20303번: 할로윈의 양아치

cpp

#include <iostream>
using namespace std;

typedef pair<int, int> team;

int N, M, K;
int Candy[30000];
int Root[30000];
bool Visited[30000];

int TeamNum;
team Team[30000];
int DP[30001][3001];

int Find(int Node)
{
‌if (Node == Root[Node])
‌{
‌‌return Node;
‌}

‌return Root[Node] = Find(Root[Node]);
}

void Union(int NodeA, int NodeB)
{
‌int A = Find(NodeA);
‌int B = Find(NodeB);

‌int Min = min(A, B);
‌Root[A] = Min;
‌Root[B] = Min;
}

void InitTeam()
{
‌cin >> N >> M >> K;

‌for (int i = 0; i < N; ++i)
‌{
‌‌cin >> Candy[i];
‌‌Root[i] = i;
‌}

‌for (int i = 0; i < M; ++i)
‌{
‌‌int A, B;
‌‌cin >> A >> B;
‌‌Union(A - 1, B - 1);
‌}

‌for (int i = 0; i < N; ++i)
‌{
‌‌if (Visited[i])
‌‌{
‌‌‌continue;
‌‌}

‌‌int R = Find(i);
‌‌Visited[i] = true;
‌‌++Team[TeamNum].first;
‌‌Team[TeamNum].second += Candy[i];
‌‌for (int j = i + 1; j < N; ++j)
‌‌{
‌‌‌if (R == Find(j))
‌‌‌{
‌‌‌‌Visited[j] = true;
‌‌‌‌++Team[TeamNum].first;
‌‌‌‌Team[TeamNum].second += Candy[j];
‌‌‌}
‌‌}

‌‌++TeamNum;
‌}
}

int DynamicProgramming()
{
‌for (int i = 1; i <= TeamNum; ++i)
‌{
‌‌int Num = Team[i - 1].first;
‌‌int Cdy = Team[i - 1].second;

‌‌for (int n = 0; n < K; ++n)
‌‌{
‌‌‌if (Num <= n)
‌‌‌{
‌‌‌‌DP[i][n] = max(DP[i - 1][n], DP[i - 1][n - Num] + Cdy);
‌‌‌}
‌‌‌else
‌‌‌{
‌‌‌‌DP[i][n] = DP[i - 1][n];
‌‌‌}
‌‌}
‌}

‌return DP[TeamNum][K - 1];
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(nullptr); cout.tie(nullptr);

‌InitTeam();
‌cout << DynamicProgramming();
}

---

 

분리집합 & 배낭 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 유니온 & 파인드 연산을 통해서 팀 정보 배열 생성

1-a. 팀 정보: 팀내의 인원, 사탕 개수

 

2. DP[팀개수][K] 행렬에 값 채우기

2-a. 일반적인 배낭 문제 풀이 방법 사용

2-b. K명의 사탕을 뺏으면 안되기 때문에 K-1까지만 채우기