[백준] 1949-우수 마을(C++)

문제링크: www.acmicpc.net/problem/1949

1949번: 우수 마을

 

• '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
• 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
• 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

위

3가지 조건을 통해서 점화식을 도출해야 합니다.

 

문제 접근 방법:

1. 모든 경우의 수를 비교해주어야 하는 것을 인지

2. 수의 범위가 10000임으로 일반적인 dfs 를 쓰면 시간 초과가 남을 인지

3. dp방식을 통해서 한번 확인한 마을이라면 마킹을 해두며 진행해야함을 인지

 

점화식은 

 

일반 마을 = 인접 마을 중에서 최대값

우수 마을 = 인접 마을 중에서 일반 마을들의 최대값 

이고 up-down방식으로 구현했습니다.

 

 

아래는 정답 코드입니다.

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

int n = 0;
bool visited[10001] = { 0, };
int cost[10001] = { 0, };
vector <int> arr[10001];
int dp[10001][2];
void dfs(int current) {
	if (visited[current])
		return;
	
	visited[current] = 1;
	int& normal = dp[current][0];
	int& greated = dp[current][1];
	normal = 0;
	greated = cost[current];
	for (int i = 0; i < arr[current].size(); i++) {
		int num = arr[current][i];
		if (visited[num] == 1) continue;

		dfs(num);
		normal += max(dp[num][1], dp[num][0]);
		greated += dp[num][0];
		
	}
}



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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
	}

	for (int i = 0; i < n - 1; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		arr[t1].push_back(t2);
		arr[t2].push_back(t1);
	}

	dfs(1);

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

	return 0;
}

dfs를 먼저 호출하고 해당 값들에 넣어주어야지 값들이 올바르게 들어갑니다.