백준 1949 : 우수 마을

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

1949번: 우수 마을

 

트리 DP문제고 근본적으로 아래 문제와 동일한 문제다.

https://unfunhy.tistory.com/107?category=825141 

백준 2533 : 사회망 서비스(SNS)

 

1. 이전 마을(부모)이 우수 마을이라면 지금 마을(자식)은 우수 마을이 될 수 없다.

2. 이전 마을이 우수 마을이 아니라면, 지금 마을은 우수마을일 수도, 아닐 수도 있다.

(우-우x-우x-우 처럼 우수마을 아닌 마을이 연속해서 두 번 나오는 경우가 있을 수 있음)

 

이를 탑다운으로 구현하면 아래와 같다.

#include <iostream>
#include <vector>

#define max(a,b) a>b?a:b
using namespace std;

int n;
int population[10'001];
vector<int> edge[10'001];
int dp[10'001][2];

int tree_dp(int cur, int prev, bool prev_selected) {
	// 메모이제이션 되어있는 경우 리턴
	if (cur != 1 && edge[cur].size() < 2) dp[cur][1] = population[cur];
	if (prev_selected && dp[cur][0]) return dp[cur][0];
	if (!prev_selected && dp[cur][1] && dp[cur][0]) return max(dp[cur][0], dp[cur][1]);

	int next, sum = 0;

	dp[cur][1] = population[cur];
	for (int i = 0; i < edge[cur].size(); i++) {
		next = edge[cur][i];
		if (next == prev) continue;

		// 현재 노드를 칠하지 않을 때
		dp[cur][0] += tree_dp(next, cur, 0);
        // 이전 노드가 칠해지지 않았다면, 현재 노드가 칠해질수도 있음
		if (!prev_selected) {
			dp[cur][1] += tree_dp(next, cur, 1);
		}
	}

	if (prev_selected) return dp[cur][0];
	else return max(dp[cur][0], dp[cur][1]);
}

void solution() {
	int n1, n2;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> population[i];
	for (int i = 0; i < n - 1; i++) {
		cin >> n1 >> n2;
		edge[n1].push_back(n2);
		edge[n2].push_back(n1);
	}

	cout << tree_dp(1, 0, 0);
}

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

	return 0;
}

메모리: 3424 kb

시간: 4 ms