프로그래밍 연습장

[BOJ 2794] MARS 본문

문제 해결/acmicpc.net

[BOJ 2794] MARS

김준원 2017. 3. 25. 20:45

나는 되게 오랫동안 고민하면서 풀었다. 풀고 나니 실행시간과 소스 길이에서 모두 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)$에 풀 수 있다.


'문제 해결 > acmicpc.net' 카테고리의 다른 글

[BOJ 8192] Sheep  (0) 2018.02.11
[BOJ 9521] 색칠 공부  (0) 2017.10.22
[BOJ 7332] 편의점 알바  (0) 2017.08.28
[BOJ 8874] 웜뱃  (0) 2017.08.27
[BOJ 14179] 크리스마스 이브  (0) 2017.08.18
[BOJ 2794] MARS  (0) 2017.03.25
0 Comments
댓글쓰기 폼