[백준/BOJ] 백준 1693번 : 트리 색칠하기

www.acmicpc.net/problem/1693 1693번: 트리 색칠하기 n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때 www.acmicpc.net 트리를 만들고 트리 DP(트리에서의 다이나믹 프로그래밍)를 이용해서 문제를 해결했는데, 100000(n의 최댓값)은 2의 16.xx승 이므로 18개의 색깔이면 충분하다는것을 이용해서 문제를 해결했다. 코드 #include #include #include using namespace std; int n; vector adj[100001]; int cache[100001][19]; //100000은 ..

2021.04.10