[ICPC 본선 대비 뇌셋] Day 6

백준 1868번 보물찾기 www.acmicpc.net/problem/1868

1868번: 보물찾기

이 문제를 본지 1주일만에 풀이를 쓰는 것 같다.

방법은 대충 생각하고 있었는데 구체화가 너무 더뎌 푸는데 오래걸렸다. 여담이지만, 내 첫 루비를 장식하게 되었다.

[시도 1] 트리의 지름일 것이다. --> 반례를 찾을 수 있다.

[시도 2] centroid decomposition을 하면 될 것이다. --> 반례를 찾을 수 있다.

일반적인 그리디를 통해서 문제를 접근하면 쉽게 반례를 찾을 수 있으므로, 생각은 결국 dfs 트리 DP로 귀결된다.

처음 트리 dp를 생각하면, 제일 처음으로는 다음 시도를 할 것이다.

[시도 3] 정점 v의 서브트리에서 최소 횟수를 dp 배열에 저장하며 dp를 갱신한다.

좋은 아이디어이지만, 아직은 부족하다. dp에 저장된 값을 갱신하려고 할 때, 자식의 dp값이 1, 2인 경우를 생각하자.

경우 1: 한 자식은 노드수가 2인 line, 나머지 자식은 노드수가 4인 line이다.

경우 2: 한 자식은 노드수가 3인 line, 나머지 자식은 노드수가 4인 line이다.

경우 1은 총 길이가 7인 line이고, 경우 2는 총 길이가 8인 line이므로, 각각 올바른 dp값은 2, 3이므로, 올바른 dp값의 수정이 일어날 수 없다.

서브트리에서 최소 횟수는 대충 log(길이)정도이고, 이 정보는 dp를 갱신하기에 충분하지 않다는 말이 된다.

그렇다면 다음과 같은 생각을 할 수 있다.

[가설 1] 정점 v의 서브트리를 특정 길이 x의 line으로 대체했을 때, v 위의 트리의 모양에 관계없이 문제의 답은 변하지 않는다.

[증명] f(v) = x라고 하자.

서브트리 T를 길이 n의 라인 L로 대체하려고 한다. 다음과 같은 규칙으로 T의 각 정점을 L와 대응시킨다.

T가 L로 대체되었다면, T의 루트에서 점을 N(>>n)개 추가했을 때, [log2(N+n)]이 문제의 답이 되어야한다. 문제의 답이 바뀌게 되는 최소의 N을 잡은 후, 그 상황에서 T의 의사결정트리를 만들고 T와 L의 의사결정트리를 만들면, T의 의사결정트리의 정점에서 L의 의사결정트리의 정점으로 가는 전사함수를 만들 수 있다.

이 함수를 이용하면 T를 L로 대체하여도 문제의 답이 변하지 않는다는 사실을 알 수 있다. 증명이 너무 길어 정현이형한테 쉬운 풀이를 맡긴다.

한편 한 정점(서브트리의 루트) v에 라인이 A개 달려있을때 문제의 답을 찾는 과정을 생각해보자.

가장 긴 길이 a를 가지는 라인이 있다고 하자. 답은 lg(a)+1이하임이 보장된다. 우리는 루트에 새로운 라인을 추가하며 얼마의 길이의 라인까지 추가했을 때 정답이 M = lg(a)+1으로 유지되는지를 확인하고 싶다. 이를 확인하면 이 서브트리를 얼마의 길이의 라인으로 대체해야하는지 알 수 있음은 자명하다.

만약 라인들의 길이의 최댓값 a에 대해서 lg(a)<M이면 루트에서 물어보고 남은 라인에 대해서 질문을 이어가면 된다. lg(a)>=M이라면, 첫번째 질문을 길이가 a인 라인의 끝에서 2^M번째 위치에 하는것이 제일 좋음을 보일 수 있다. 따라서 원래 수열에서 a를 빼고, 길이 - 2^M을 넣는다.(priority_queue를 사용하면 편하다.) 첫번째 질문을 했으므로, 남은 질문은 M-1개이다. 새로운 길이들이 주어졌으므로, 이 과정을 M번 진행하여 이 트리에서 문제의 정답이 lg(a)+1보다 큰지 아닌지를 결정할 수 있다. 대체될 라인의 길이를 이분탐색으로 구할 수 있다.

이제 dfs를 돌면서 대체할 라인의 길이를 찾으면 된다.

정답은 최종 라인의 길이를 A라고 할 때, lg(A)가 된다.

상당히 어려운 문제였다.

 

훨씬 쉬운 풀이가 있었다.ㅋㅋ 강한필님이 써주신 풀이로 링크를 남긴다.

www.secmem.org/blog/2019/07/20/Optimal-Search-On-Tree/

이진탐색의 확장 - 트리에서의 효율적인 탐색