취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 32521번 문제인 팩트는 트리가 건강해지고 있다는 거임이다.
문제는 아래 링크를 확인하자.

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

주어진 트리를 1번 노드를 루트로 갖는 트리로 생각해보자. 이 때, (루트가 아닌) n번 노드를 루트로 갖는 서브트리에 대하여 해당 서브트리에 포함된 '안 건강 노드'의 개수가 \(K\)개를 넘으면 적어도 해당 서브트리의 에지 중 하나를 지워야 함을 관찰할 수 있다. 또한 \(K\)개를 넘지 않으면 해당 서브트리의 에지를 지우는 것보다는 서브트리의 루트와 그 부모 노드를 잇는 ㅂ에지를 지우는 것이 항상 상대적 이득임을 관찰할 수 있다.

위에서 관찰한 정보를 이용하면, 1번 노드에서 시작해 dfs를 하면서 '안 건강 노드'의 개수가 \(K\)개를 넘는 서브트리를 만날 때마다 적절하게 해당 서브트리의 루트와 자식 노드를 잇는 에지를 지워 문제를 해결할 수 있을 것임을 유추할 수 있다. 이 때, 더 많은 '안 건강 노드'를 갖는 서브트리와 이어지는 에지부터 그리디하게 지워야 함은 어렵지 않게 관찰할 수 있다.

아래는 제출한 소스코드이다.

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

int N, K, ans;
int A[100001];
vector<int> G[100001];

int dfs(int cur, int par) {
	int ret = A[cur];
	vector<int> vec;
	for (auto &nxt:G[cur]) {
		if (nxt == par) continue;
		int tmp = dfs(nxt, cur);
		if (!tmp) continue;
		vec.emplace_back(tmp);
	}
	int vsize = vec.size(), idx = 0;
	sort(vec.begin(), vec.end());
	while (idx < vsize && ret + vec[idx] <= K) {
		ret += vec[idx];
		idx++;
	}
	ans += vsize - idx;
	return ret;
}

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	dfs(1, 1);
	cout << ans;
}