BOJ 12736 - Fireworks

오늘은 원래 문제를 좀 더 풀려다가 교내 대회 등의 이슈로 바빠서 한 문제만 풀기로 마음먹었다. 이왕 푸는거 좀 좋은 문제를 풀어야 할 것 같았기 때문에 클10이면서 북마크에 정말 오래 있던 문제를 잡게 되었다. 유명한 문제이고 솔브 수도 많은데 시중에 적당한 자료가 없는 것 같아 풀이를 작성하려 한다.

 

문제 요약

 

가중치 있는 무향 트리가 주어지며, 간선 하나를 골라 가중치를 1만큼 변화시키는 연산을 할 수 있다. 1번 정점에서 모든 리프 정점까지의 거리를 모두 같게 하기 위해 필요한 연산의 최소 횟수를 구하여라.

 

풀이 (생각의 흐름)

 

BOJ에서 풀었기 때문에 섭태는 잘 몰라 만점 풀이 기준으로 설명하겠다.

 

\(dp(v,x)\) = \(v\)번 정점을 루트로 하는 서브트리에서 리프 정점까지의 거리를 \(x\)로 만들기 위해 필요한 최소 비용으로 정의하자. 이러한 정의는 트리 DP에 익숙하다면 어렵지 않게 떠올릴 수 있을 것이다.

 

만약 가중치가 모두 작다면 위의 DP 정의를 그대로 사용해 문제를 해결할 수 있지만, 그러기에는 정점의 수와 가중치 모두 너무 크다. 따라서 DP를 잘 최적화해야 하는데, 이를 위해 DP 값의 개형을 분석해보자.

 

DP를 최적화하는 방법에는 여러 가지가 있는데 왜 개형 분석을 시도해야 하는 걸까? 그 이유는 저 정의에서의 DP가 좋은 개형을 가지기 때문이다. 문제 상황에 의해 비용은 결국 절댓값 함수를 적절히 조작해 나온 모양이 될 것이고, 이는 관리해주기 용이한 성질을 여럿 가진다. 성게 그래프 등의 몇 가지 예시를 직접 그려보면 도움이 될 것이다.

 

위 내용, 정확히는 절댓값 함수의 특성에 의해 \(dp(v,x)\)는 각 부분이 일차함수들로 이루어진 볼록한 모양을 띈다. 정확하게 같지는 않지만 절댓값 함수를 여러 개 더한 모습을 상상하면 편하다. 이제 이를 이용해 DP값을 계산해주어야 하는데, 일단 내 경험에는 이를 식으로 풀어내려고 하면 오히려 복잡해지는 것 같다. 따라서 식이 아닌 조금 다른 방법으로 이를 설명해보고자 한다.

 

\(v\)의 자식 노드를 \(c\), 두 정점 사이의 간선의 가중치를 \(l\)이라 하자. 우리의 목표는 \(dp(c,x)\)와 \(l\)을 바탕으로 \(dp(v,x)\)가 어떻게 생겼을지 알아내는 것이다.

 

\(dp(c,x)\)에서 기울기가 바뀌는 점들의 \(x\)좌표를 차례로 \(x_1, \cdots, x_k\), 이를 기준으로 나뉘는 각 선분의 기울기를 \(a_0, \cdots, a_k\)라 하겠다. 또한, \(a_{i-1} \le -1\)인 최대의 \(x_i\)를 \(x^{*}\)라 하자.

 

우선, 자명히 \(dp(v,0) = dp(c,0) + l\)이다. 즉, 모든 간선의 가중치를 0으로 만든 후 1씩 늘려 나갈 것이다. 만약 이때 \(x \le x^{*}\)이라면 \(dp(c,x)\)값을 그대로 쓰는 것이 이득이다. \(l\)을 늘이면 비용이 1씩 감소하는 반면에 기존 트리에서 늘이면 \(x^{*}\)의 정의에 의해 비용이 적어도 1만큼 감소하기 때문이다. 이렇게 \(x^{*}\)에 도달했다면 줄여두었던 \(l\)을 피며 비용을 1씩 줄이고, 그 이후에는 만약 \(dp(c,x)\)에 기울기가 0인 직선이 있다면 이를 사용, 여기까지 모두 사용했다면 다시 \(l\)을 늘려 비용을 1씩만 추가하는 것이 최적이다.

 

이를 정리해서 설명하면
1. 기울기가 -1 이하인 마지막 직선 뒤에 기울기가 -1이고 길이가 \(l\)인 선분을 추가한다. 이때 길이는 선분의 길이가 아니라 \(x\)축에 사영해 본 길이이다.

2. 기울기가 1 초과인 직선은 모두 1로 만든다.

3. 이때 y좌표는 모두 \(l\)씩 증가한다.

 

자식 -> 부모로 올라올 때는 이렇게 관리해주면 되고, 부모 정점에서 여러 자식의 DP값을 합치는 것은 그냥 그대로 더해주면 된다.

 

이제 이를 어떻게 관리할지만 생각하면 된다. 트리 문제를 해결하는 것이 익숙한 사람이라면 뭔가 선분의 집합을 저장해 small to large 기법으로 합쳐주고 싶다는 생각이 들 것이다. 이는 반은 맞고 반은 틀린 생각인데, 선분의 형태를 그대로 저장하려 하면 두 집합을 합칠 때 두 집합의 원소를 모두 보아야 정보를 온전히 전달할 수 있다. 따라서 큰 집합의 원소를 보지 않아도 관리가 잘 되는 형태를 찾아야 한다.

 

이는 간단하지만 발상해내기 정말 어려운 아이디어로 해결할 수 있는데, 그래프의 변곡점의 \(x\)좌표를 집합으로 관리하면 된다. 만약 기울기가 1보다 크게 변하는 점이 있다면 그만큼의 같은 좌표를 저장하고 있어야 함에 유의하자. 이렇게 하면 그냥 두 집합을 더해주는 것만으로 두 그래프를 합칠 수 있다.

 

저장하는 정보가 단순해졌기 때문에 구현에 유의를 더 해야 하는데, 예를 들어서 기울기가 1 초과인 직선의 개수를 판단하고 지우는 부분이 대표적이다. 이는 함수 \(dp(v,x)\)에서 가장 기울기가 작은 부분의 기울기가 (루트를 \(v\)로 하는 서브트리에서 리프 노드의 개수)임을 이용해 처리해줄 수 있다.

 

이제 함수 \(dp(1,x)\)의 최솟값이 답이 된다. 이는 \(dp(1,0)\), 즉 그래프의 y절편이 자명하게 모든 간선의 가중치의 합임을 이용해 기울기가 음수인 간선을 직접 따라가면서 최솟값에 도달한 후 이를 출력해주면 된다.

 

유명한 문제라 핵심 태그 정도는 알고 들어갔는데, 그럼에도 배울 부분이 많았다. 요즘 문제 풀면서 OI 문제들이 PS의 정수라는 말을 좀 체감하고 있다. 물론 월파에는 이런 문제들은 안 나올 확률이 높다. 그래도 추천합니다.