백준 1693 트리 색칠하기

문제링크 : https://www.acmicpc.net/problem/1693

아이디어

• 부모트리 아래 모든 비용 : 자식 트리를 기준 아래 모든비용 + 부모트리 색
• 자식노드의 값을 재활용 가능 > Tree DP
  • Tree DP는 인접리스트를 단방향 리스트로 만들어줘야함
• DP[N][K] : N번 노드가 K색을 칠할떄 최소비용
• 점화식 : DP[N][K] = min(DP[N-1][0] ~ DP[N-1)[K-1], DP[N-1][K+1] ~DP[N-1][KK]) + 다른 자식노드 + 부모노드 색
  • 부모노드 DP값 = 자식노드 해당 색깔 제외한 최소값의 합 + 부모노드색
• 색을 N색 모두 하면 메모리초과 발생
  • 모든 색을 사용하지 않아도됨
  • 계산에 따라서 lgN색까지만 구하면됨, 넉넉하게 20개 구해보자

시간복잡도 계산

• 모든 노드 * lgN개의 색
• O(N*lgN) > 가능

자료구조

• 인접 리스트 : vector adj[100010]
• 단방향 리스트 : vector tree[100010]
• dp값 : int dp[100010][21]

코드(C++)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <iostream> #include <vector>   using namespace std;   const int inf = 1e8+10; vector<int> adj[100010]; vector<int> tree[100010]; int dp[100010][30];   void make_tree(int cur, int pre) {     for(int x : adj[cur]) {         // 이전노드에서 넘어 온경우 건너뜀         if(x == pre) continue;         tree[cur].push_back(x);         make_tree(x, cur);     } }   int get_dp(int node, int color) {     if(dp[node][color] != -1) return dp[node][color];          int ans=0;     // 자식노드 dp 값 모두 더한다음 부모노드 색 더해서 리턴'     // 이떄 자식노드는 같은 색깔 아니어야함     for(int x : tree[node]) {         int minv = inf;         for(int k=1; k<=20; k++) {             if(color == k) continue;             minv = min(minv, get_dp(x, k));         }         ans += minv;     }          return dp[node][color] = ans + color; } int main() {     ios::sync_with_stdio(0);     cin.tie(0);          // dp를 가장 아래노드부터 구하는게 어려움     // 그래서 top-down 방식으로 root 노드에서부터 구하자     // 그럼 -1로 초기화해서 처리 된것인지 아닌지 구분해야함     fill(&dp[0][0], &dp[100009][30], -1);          int N; cin >> N;     for(int i=0; i<N-1; i++) {         int a,b; cin >> a >> b;         adj[a].push_back(b);         adj[b].push_back(a);     }          // 단방향 리스트 만들기     make_tree(1,-1);          int minv = inf;          for(int i=1; i<=20; i++) {         // 1번노드의 1~20색깔을 가질때 최소값 구하기         minv = min(minv, get_dp(1, i));     }          cout << minv << '\n';     return 0; }   Colored by Color Scripter

cs

문제유형

• DP - Tree DP
  • 자식노드의 값을 재활용 할 수 있을 때 Tree DP 사용 가능
  • 기존의 DP와 다른점은, 간선으로 연결된 노드에 DP를 적용

비슷한 문제

• https://www.acmicpc.net/problem/2533