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

https://www.acmicpc.net/problem/12995 12995번: 트리나라 트리나라는 N개의 도시로 이루어져 있고, 각각의 도시는 1번부터 N번까지 번호가 매겨져 있다. 트리나라의 도로 체계는 트리를 이룬다. 즉, 트리나라에는 N-1개의 양방향도로가 있다. 또, 모두 연 www.acmicpc.net cache[서브트리의 루트번호][마을을 고를 개수]에 경우의 수 (해당 서브트리에서 해당 개수의 마을을 고르는 경우의 수)를 bottom-up 방식으로 채워나가는 방법을 통해 문제를 해결했다. sub_tree_size[there]부터 확인해야 되는데, 작은 것부터 시작하면 이번 순서에 만들어진 것을 이번 순서에 영향을 줄 수 있다(이용할 수 있다) 코드 #include #include #inc..

2021.09.01