[BOJ 2794] MARS

http://www.acmicpc.net/problem/2794

나는 되게 오랫동안 고민하면서 풀었다. 풀고 나니 실행시간과 소스 길이에서 모두 1등을 했다! 기분이 너무 좋아서 풀이를 어디에라도 쓰고 싶어 쓰는 첫 글이다.

먼저 $n=2^{k}$ 라고 하자. 나는 $O(n^{2}\log n)$에 풀었다.

2차원 배열에 대한 DP로 푼다.

$dp(x, y):=$ $x$번째부터의 수열에 대한 답. 이 때까지의 수열의 마지막 $x$번째 수는 $y$이다.

이렇게 정의해도 되는 이유는 마지막 수가 $y$라는 정보가 다음 수가 무엇이어야 하는지에 대한 큰 힌트를 제공해주기 때문이다. 정확히는, $1$부터 $n$까지의 수로 이진 트리를 만들었을 때, $x$번째와 $x+1$번째 노드의 LCA의 오른쪽 자식에 있는 원소들만 돌면 되는 것이다.

위와 같이 $dp$ 배열을 정의하고 가능한 다음 수들에 대해 모두 돌아보는 형식으로 구현하면 $O(n^2\log n)$의 시간에 정답이 나온다.

이 때 다음 수의 후보(상태 전이의 가짓수)가 어떤 수 다음에는 최대 $n/2$개도 있을 수 있어 $O(n^3)$이라 생각할 수도 있지만, 평균적으로 $O(\log n)$개의 후보만이 존재하기 때문에 $O(n^2\log n)$에 풀 수 있다.