문제 링크
- http://icpc.me/11755
문제 출처
- 2015 Japan Regional I번
시간복잡도
- $O(3^{N/3})$
풀이
N ≤ 40이기 때문에 완전탐색은 불가능합니다. 가지치기를 열심히 해줘야 합니다.
위 그림과 같은 그래프에서 1 -> 2 -> 3 -> 5 -> 6으로 이동했고, 6번 정점에서 어디로 갈지 결정해야하는 상황을 생각해봅시다.
과연 6번 정점에서 4번 정점으로 가는 경로를 탐색을 해봐야할까요? 그렇지 않습니다.
일단 위 그림처럼 4번에 추가적인 정점이 안 붙어있는 경우에는, 4번에 있는 사람들이 전부 3번 정점으로 몰려갔기 때문에 고려할 필요가 없습니다.
이 그림처럼 4번 정점에 추가적인 정점이 붙어있는 경우에는 4’번 정점때문에 고려를 해야할 것 같지만, 탐색할 필요가 없습니다.
6에서 4로 가는 것보다, 이전에 4와 마주친 3번 정점에서 바로 가는 것이 항상 이득이기 때문이죠.
그러므로 4번 정점을 굳이 방문할 필요가 없습니다.
조금 더 정확히 말하자면, cnt[i]가 현재까지의 경로에서 i와 인접한 정점의 개수라고 할 때 cnt[i] ≥ 2인 정점으로 이동할 필요가 없습니다.
이 전략만 이용해 가지치기를 해도 $O(3^{N/3})$이라는 이상한 시간복잡도가 보장이 되기 때문에 AC를 받을 수 있습니다.
$T(N)$을 N개의 정점이 주어질 때의 연산량이라고 정의합시다.
$T(N) = \displaystyle \max_{d}(d * T(N-d))$(정점들의 차수)입니다. 각 정점으로 인해 d개의 정점의 cnt가 증가해 탐색 범위를 좁혀주고, 인접한 정점에 대해 각각 재귀 호출을 해주기 때문입니다.
이때 $T(N)$은 1부터 N까지의 정수를 잘 골라서 합을 N으로 만들 때의 곱의 최댓값과 동일합니다. 이 값이 $O(3^{N/3})$이라는 것을 증명하면 됩니다.
4 이상인 어떤 정수 a는 2와 a-2로 쪼개줄 수 있고, 2a-4 ≥ a이기 때문에 4 이상인 정수는 2와 a-2로 항상 쪼개도 됩니다.
이제 1 2 3만 남게 됩니다. 6을 만드는 방법은 2를 3개 더하는 방법과 3을 2개 더하는 방법이 있는데, $2^3 < 3^2$이므로 3을 2개 더하는 것이 더 이득입니다.
그러므로 최대 $3^{N/3}$이 됩니다.