[백준/BOJ] 백준 12995번 : 트리나라

[백준/BOJ] 백준 12995번 : 트리나라

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

cache[서브트리의 루트번호][마을을 고를 개수]에 경우의 수 (해당 서브트리에서 해당 개수의 마을을 고르는 경우의 수)를 bottom-up 방식으로 채워나가는 방법을 통해 문제를 해결했다. sub_tree_size[there]부터 확인해야 되는데, 작은 것부터 시작하면 이번 순서에 만들어진 것을 이번 순서에 영향을 줄 수 있다(이용할 수 있다)

코드

#include #include #include #include using namespace std; int n, k; vector adj[51]; vector parent(51, 0); vector children[51]; vector sub_tree_size(51, 1); vector maked(51, 0); vector order; vector> cache(51, vector(51, 0));//[서브트리의 루트번호][마을을 고를 개수] = 경우의 수 (해당 서브트리에서 해당 개수의 마을을 고르는 경우의 수) void Pre() { for (int i = 0; i < 51; i++) { cache[i][1] = 1; //어떤 서브트리더라도 1개의 도시를 고르는 경우는 해당 서브트리의 루트를 고르는 하나의 경우이다 cache[i][0] = 1; } } void MakeTree(int here) { maked[here] = 1; for (int i = 0; i < adj[here].size(); i++) { int there = adj[here][i]; if (maked[there] == 0) { MakeTree(there); parent[there] = here; children[here].push_back(there); sub_tree_size[here] += sub_tree_size[there]; } } } void Travel(int here) { queue q; q.push(here); while (!q.empty()) { int here = q.front(); q.pop(); order.push_back(here); for (int i = 0; i < children[here].size(); i++) { int there = children[here][i]; q.push(there); } } reverse(order.begin(), order.end()); } int Solve() { //아래쪽부터 확인한다 for (int i = 0; i < order.size(); i++) { int here = order[i]; int there = parent[here]; //here의 부모노드 //here가 루트노드일때 if (there == 0) continue; //for (int j = 2; j <= sub_tree_size[there]; j++) //무조건 sub_tree_size[there]부터 확인해야 된다 작은것 부터 시작하면 이번순서에 만들어진것을 이번순서에 이용할 수 있다 //bottom-up 방식으로 접근 for (int j = sub_tree_size[there]; j >= 2; j--) { //자식노드쪽에서 a개를 고르는 경우 for (int a = 1; a <= sub_tree_size[here]; a++) { //a는 0 ~ sub_tree_size[here] //a + b = j int b = j - a; //부모노드쪽의 서브트리에서 b개를 고른다 if (b <= 0) continue; cache[there][j] = (cache[there][j] + (cache[here][a] * cache[there][b] % 1000000007)) % 1000000007; } } } int ret = 0; for (int i = 1; i <= n; i++) { ret = (ret + cache[i][k]) % 1000000007; } return ret; } int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); Pre(); cin >> n >> k; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } MakeTree(1); //1번 정점이 루트인 트리를 만든다 Travel(1); cout << Solve(); return 0; }

from http://geniusjo-story.tistory.com/499 by ccl(A) rewrite - 2021-09-01 14:26:28