[백준] 12978 - 스크루지 민호 2

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

12978번: 스크루지 민호 2

 

자주 보이는 유형의 트리-dp 문제이다.

dp[i][j] = j가 0일 때, i번째 도시에 경찰서를 세우지 않았을 때, j가 1일 때, i번째 도시에 경찰서를 세웠을 때 하위 서브 트리에 세워야 하는 최소 경찰서의 수로 정의하였다.

 

j가 0일때는, 해당 정점에 경찰서를 세우지 않으므로 그 자식 노드들에는 무조건 경찰서를 세워야 한다.

j가 1일때는, 해당 정점에 경찰서를 세우므로 그 자식 노드들에는 경찰서를 세우거나, 세우지 않을 수 있다.

 

따라서 다음과 같이 구현할 수 있다.

 

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

int n, dp[100001][2];
vector<vector<int>> v;

int go(int node, int pre, int c) {

	if (dp[node][c] != 0) return dp[node][c];

	int ret = 0;

	for (auto& i : v[node]) {
		if (i != pre) {
			if (c == 1) {
				ret += min(go(i, node, 1), go(i, node, 0));
			}
			else {
				ret += go(i, node, 1);
			}
		}
	}

	return dp[node][c] = ret + c;
}

int main() {

	cin >> n;
	v.resize(n + 1);

	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	cout << min(go(1, 0, 0), go(1, 0, 1));
	return 0;
}