[BOJ 1693] 트리 색칠하기

문제

www.acmicpc.net/problem/1693

1693번: 트리 색칠하기

 

---

풀이

트리DP를 사용합니다.

트리가 주어졌을 때 배열 \(dp\)를 다음과 같이 정의할 수 있습니다:

 

\(dp[i][j]:\) \(i\)의 색이 \(j\)일 때 \(i\)를 루트로 하는 서브트리의 총 비용의 최솟값.

 

여기서 \(j\)를 \(1\)부터 \(N\)까지 전부 다 구하면 \(N\)의 범위가 \(1\)이상 \(100000\)이하이기 때문에 시간초과가 날 수 있습니다.

www.acmicpc.net/board/view/13972의 글을 보니 최악의 경우 사용되는 색의 가짓수가 \(\log_{2} N\)임을 알 수 있었습니다.

트리를 순회하면서 \(dp[i][j]\)에 값을 저장해 나가면 쉽게 풀 수 있습니다.

 

시간복잡도: \(O(N \log N)\)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int N, max_num;
vector<vector<int>> graph;
vector<vector<int>> dp;

void solve(int cur, int pnode) {
    for (auto next : graph[cur]) {
        if (next == pnode) continue;
        solve(next, cur);
        for (int i = 1; i <= max_num; ++i) {
            int mn = 1e9;
            for (int j = 1; j <= max_num; ++j)
                if (i != j)
                    mn = min(mn, dp[next][j]);
            dp[cur][i] += mn;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    max_num = (int)floor(log2(N));
    graph.resize(N + 1);
    dp.resize(N + 1, vector<int>(max_num + 1));
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 0; i <= N; ++i)
        for (int j = 1; j <= max_num; ++j)
            dp[i][j] = j;

    solve(1, 0);

    int mn = 1e9;
    for (int i = 1; i <= max_num; ++i)
        mn = min(mn, dp[1][i]);
    cout << mn << "\n";

    return 0;
}