2197번: 분해 반응

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


$O(n^3)$

dp[n][m]: n번 노드를 루트로 하는 서브트리에서 다음 조건을 만족하는 분자를 만들기 위해 필요한 최소 분해 반응 회수
- n번 원자를 포함한다.
- m개의 원자는 직, 간접적으로 연결되어 있다.(즉, m개 원자 중 임의의 i,j번 원자 사이에 경로가 존재)

dfs를 이용해 dp을 한다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int dp[151][151], n, m, r = 1e9;
vector<int> adj[151];
void f(int h, int p) {
    dp[h][1] = 0;
    for (auto it : adj[h]) {
        if (it == p) continue;
        f(it, h);
        for (int i = n; i; i--) {
            dp[h][i]++;
            for (int j = 1; j < i; j++) dp[h][i] = min(dp[h][i], dp[h][j] + dp[it][i - j]);
        }
    }
    r = min(r, dp[h][m] + 1 - !p);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    fill(&dp[0][0], &dp[150][151], 1e9);
    f(1, 0);
    printf("%d", r);
    return 0;
}