[BOJ 17435]

문제 바로가기 : https://www.acmicpc.net/problem/17435
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

sparse table

희소 테이블(Sparse Table)은 여기에서 참고했습니다. 감사합니다.

BOJ 3584에서 이용했던 parent[u][k]를 이해했다면 어렵지 않다.
parent[u][k]는 u의 2^k번째 부모로 접근한다는 말인데, 1, 2, 4… 번째의 부모 정보를 모두 담았기 때문에
(m != 2^n 이어도) m번째 부모까지 빠르게 접근 가능하다. 자세한 내용은 링크를 참고.

review

어제 하루종일 LCA때문에 고생을 했더니 이 문제를 푸는데는 그렇게 어렵지 않았다. 배운 내용중 일부라서 그런가?
LCA에서 두 노드의 깊이 차이가 존재한다면 차이가 없도록 깊이를 맞춰주는 매커니즘이 답을 내는 힌트였다.
물론 각 노드별로 2^k번째 부모의 정보를 담는다는 전제하에 가능하다.

int query(int cur, int n) {
    for (int i = COL-1; i >= 0; i--) {
        if (parent[cur][i] != -1 && n >= (1<<i)) {
            cur = parent[cur][i];
            n -= (1<<i);
        }
    }

    return cur;
}

n >= (1<<i)는 n >= 2^i를 말한다.
10진수인 n은 2진수로 얼마든지 표현할 수 있다. 가령 n=11010(2)이라고 하자.
i가 COL-1 즉 19부터 0으로 줄어가기 때문에 제일 앞자리인 2^4부터 카운트를 할 수 있다.
근데 2^i가 n보다 크게 되면 카운트를 할 이유가 없으니 제외되는 범위로 설정해줬다.
말로 설명하니 조금 난해한데.. 헷갈린다면 천천히 숫자를 써가며 이해하는게 더 쉬울 수 있겠다.