문제

문제 링크

문제 접근

  • 딱 트리에 디피 쓰면 될 문제로 보인다.
  • 근데 문제는…. 디피를 쓰기에 노드개수 최대 10만개, 색깔개수 10만개??
  • 그럼 dp[100001][100001]인데 말이 안되잖아..
  • 이때 등판한 구원투수 구사과님 ㅠㅠ

색깔의 수 정하기 증명(갓구사과님)

  • 그렇다면 색깔은 log_2(100000)개 최대 16개의 색깔을 가지게 된다.
  • 이를 디피를 이용해서 풀어내면 된다.

How dp

  • 현재 노드의 16개 각각의 색깔을 결정하는데 있어서 자식 노드의 현재 확인하려는 색상을 제외한 값 중 제일 작은 값을 더해준다.
  • 모든 덧셈이 끝나면 현재 노드에 각 색깔을 추가했을시의 값을 추가해준다.
  • 그리고 마지막으로 1번 노드에 저장된 값 중 가장 작은 값을 찾아낸다.

코드

#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

int n, cnt, v1, v2, visited[100001];
int dp[100001][16];
vector< vector<int> > e;
void find(int x){
    int c = e[x].size();
    for(int i = 0; i < c; i++){
        int nx = e[x][i];
        if(visited[nx])continue;
        visited[nx] = 1;
        find(nx);
        for(int j = 1; j < cnt; j++){
            int m = 987654321, mi = 0;
            for(int k = 1; k < cnt; k++){
                if(j == k)continue;
                if(m > dp[nx][k])m = dp[nx][k], mi = k;
            }
            dp[x][j] += m;
        }
    }
    for(int i = 1; i < cnt; i++)dp[x][i] += i;
    return;
}

int main(){
    n = readInt();
    cnt = log2(n) + 1;
    e = vector< vector<int> >(n + 1);
    for(int i = 0; i < n - 1; i++){
        v1 = readInt(), v2 = readInt();
        e[v1].push_back(v2);
        e[v2].push_back(v1);
    }
    visited[1] = 1;
    find(1);
    int ans = 987654321;
    for(int i = 1; i < cnt; i++){
        if(ans > dp[1][i])ans = dp[1][i];
    }
    printf("%d", ans);
}

느낀점

  • 색깔의 개수를 증명하는 과정에서 지려버렸다.
  • 나머지를 구현해낸 것이 전혀 대단해 보이지 않을 만큼 증명 자체가 너무 대단했다.
  • 음… 나도 보고 공부좀 해봐야겠다.