[BOJ] 1949 우수 마을

(2021년 1월 12일에 작성한 글입니다.)

 

1949번: 우수 마을

 

트리DP!

예전에 DP 몰아서 공부할 때 충격받았던

함수의 재귀를 이용한 방식이다.

겨울 ​신촌연합 알고리즘 캠프 중급 스터디에서 다뤘다.

​

3번째 조건을 어떻게 처리하면 되는지가 까다로운데

강사님께서 3번 조건은 무시하면 된다고 하셨다.

그렇다.

무시하면 된다.

​

내가 이해한 방법은

두 번째 조건 때문에 일단 우수마을끼리는 인접할 수 없는 상황이다

만약 n번째 마을이 우수마을이 아니고, 인접한 우수 마을이 없다고 가정하자.

이때 우리는 우수 마을들의 사람 수를 최대로 하고 싶기 때문에

n번째 마을을 우수마을로 바꾸거나, 인접한 마을 중 하나 이상이 우수마을이 될 때

우리가 원하는 최댓값이 나온다.

​

즉, 최댓값을 구하는 과정을 진행하다 보면

세 번째 조건은 따로 처리하지 않아도 알아서 처리가 된다.​

신기하다!

 

처음에 틀렸던 이유는

우수 마을의 최대 인원을 구해야 하니까

*max_element(dp[1].begin(), dp[1].end())을 답으로 출력했다.

​

근데 그러면 안 된다.

재귀는 1번 마을에서 끝나고

1번 마을이 우수 마을일때와 그렇지 않을때의 최댓값이 각각 저장되어 있을 것이기 때문에

답은 max(dp[0][1], dp[1][1])이다.

int N;
vector<int> people;
vector<vector<int>> adj;
vector<vector<int>> dp;
vector<bool> chk;
void sol(int);

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

	cin >> N;
	people.resize(N + 5);
	for (i = 1; i <= N; i++) {
		cin >> people[i];
	}
	adj.resize(N + 5);
	for (i = 0; i < N - 1; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	dp.resize(2, vector<int>(N + 5, -1));
	chk.resize(N + 5, false);
	chk[1] = true;
	sol(1);
    
	cout << max(dp[0][1], dp[1][1]) << ENDL;

	return 0;
}

void sol(int cur)
{
	if (dp[0][cur] != -1) {
		return;
	}

	dp[0][cur] = dp[1][cur] = 0;
	for (int next : adj[cur]) {
		if (chk[next]) {
			continue;
		}
		chk[next] = true;
		sol(next);
		dp[0][cur] += max(dp[0][next], dp[1][next]);
		dp[1][cur] += dp[0][next];
	}
	dp[1][cur] += people[cur];

	return;
}