백준 / 1949 우수 마을 C++

www.acmicpc.net/problem/1949

1949번: 우수 마을

트리 구조로 이루어진 마을에서 우수마을을 주민의 최대값으로 고르는 문제입니다.

조건은 다음과 같습니다.

1. 우수마을의 주민의 수 합을 최대로 한다.

2. 우수마을끼리는 인접이 불가하다.

3. 우수마을이 아닌 마을은 적어도 하나의 우수마을과 인접하다.

 

처음에 풀 때는 3번의 적어도라는 조건을 안 보고 풀어 그냥 depth별로 홀,짝 구분해서 합이 최대치인 것을 뽑으면 될 줄 알았지만, 적어도 하나의 우수마을과 인접하면 되므로 1,4 번이 우수마을, 2,3번이 아닐 때, 1-2-3-4로 연결되어도 됩니다. 

그러므로 루트 노드부터 탐색을 할 때 현재 노드가 우수마을이면 다음 마을은 무조건 안 되고, 현재 노드가 우수마을이 아니면 다음 마을은 되던 안 되던 상관없습니다. 

 

dp[i][0] :  현재 노드가 우수마을 아닐 때, i를 루트로 하는 서브트리의 가능한 최댓값

dp[i][1] : 현재 노드가 우수마을 일 때, i를 루트로 하는 서브트리의 가능한 최댓값

 

dp[i][0] += max(dp[next][0], dp[next][1])

dp[i][1] += dp[next][0]

 

결국 최댓값을 구하는 문제이고, 주민의 수가 음수인 경우는 없으므로, 세 마을이 연속해서 우수 마을로 선정되는 경우는 없습니다.

 

코드는 다음과 같습니다.

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

int n;
int people[10001];
vector<int>town[10001];
int dp[10001][2];
bool check[10001];

void make_town()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> people[i];
		check[i] = false;
		dp[i][1] = 0;
		dp[i][0] = 0;
	}
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		town[a].push_back(b);
		town[b].push_back(a);
	}
}

// 현재 노드가 우수마을이면 다음 마을은 무조건 안 됨
// 현재 노드가 우수마을 아니면 다음 마을은 상관 없음
// dp[i][0] : i번 마을이 우수마을 아닐때 최대값
// dp[i][1] : i번 마을이 우수마을 일때 최댓값
// dp[i][0] = dp[i][0] + max(dp[next][0], dp[next][1])
// dp[i][1] = dp[i][1] + dp[next][0]
// 최댓값을 구하는 것이므로 세 마을 연속 선정 안되는 경우 없음
void dfs(int node)
{
	// 선정되었을 때 안 되었을 때 기본값
	dp[node][0] = 0;
	dp[node][1] = people[node];
	check[node] = true;

	for (int i = 0; i < town[node].size(); i++) {
		int next = town[node][i];
		if (check[next] == false) {
			dfs(next);
			dp[node][0] += max(dp[next][0], dp[next][1]);
			dp[node][1] += dp[next][0];
		}
	}
}

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

	make_town();
	int root = 1; // 트리이므로 편의상 1을 루트로 잡음
	dfs(root);

	cout << max(dp[root][0], dp[root][1]);
}