백준 2197번 분해 반응

 

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

2197번: 분해 반응

N이 작아서 dp를 좀 복잡하게 짜도 된다.

나는 N*(N + 1)로 벡터를 만들어서 dp[i][j] = i번 노드를 루트로 하는 j개의 노드를 가진 서브트리의 최소 분해 반응 회수로 두었고 부모노드와 자식노드의 서브트리를 합칠때 노드 수는 더해지고 문해 반응 횟수는 서로를 연결하는 간선을 제외해서 둘의 값을 더하고 2를 빼면 되니 점화식은 dp[i][j + n] = min(dp[i][j + n], dp[i][j] + dp[i의 자식노드][n] - 2) 이다.

 

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

int ans = 1000, M, N;
vector<vector<int>> tree, dp;

void dfs(int a, int b){
	dp[a][1] = tree[a].size();
	if (M == 1) ans = min(ans, (int)tree[a].size());
	for (const int& i : tree[a]){
		if (b == i) continue;
		vector<vector<int>> ddp = dp;//같은 자식노드를 두번 더하지 않기 위해 결과값은 따로 분리해서 보관
		dfs(i, a);
		for (int j = 0; j <= N; j++){
			for (int n = 0; j + n <= N; n++){
				ddp[a][j + n] = min(ddp[a][j + n], dp[a][j] + dp[i][n] - 2);
				if (j + n == M) ans = min(ans, ddp[a][j + n]);
			}
		}
		dp = ddp;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int A, B;
	cin >> N >> M;
	tree.resize(N);
	vector<int> fill(N + 1, 1000);
	dp.resize(N, fill);

	for (int i = 1; i < N; i++){
		cin >> A >> B;
		tree[--A].push_back(--B);
		tree[B].push_back(A);
	}

	dfs(0, -1);

	cout << ans << '\n';

	return 0;
}