백준12008 262144

작성일 | In

문제 링크

  • http://icpc.me/12008

문제 출처

  • 2016 USACO US Open Platinum 1번

사용 알고리즘

  • DP
  • Sparse Table

시간복잡도

  • $O(N log N)$

풀이

[i, k] 구간을 잘 합쳐서 X를 만들고, [k+1, j] 구간을 잘 합쳐서 X를 만들어주면 [i, j] 구간에서 X+1을 만들 수 있다는 점을 이용해 문제를 풀어봅시다.

D(i, j)를 i번째부터 k번째 원소까지 사용해서 하나의 수 j를 만들 때 k+1라고 정의합시다. 그러한 k가 존재하지 않는다면 -1이나 0 등으로 초기화하면 됩니다.
예를 들어 주어진 배열이 {1, 1, 1, 2}라면 2번째부터 4번째 원소까지 사용해 3을 만들 수 있으므로 D(2, 3) = 5입니다.

배열의 각 원소는 최대 40이므로 DP Table에서 j는 최대 $40 + log_2 N$입니다. 상태의 개수는 충분히 적으니, 상태 전이만 잘 해주면 문제를 풀 수 있습니다.

위에서 말한 것을 다시 가져와보면, [s, e]를 X로 만들기 위해서는 [s, k]와 [k+1, e]를 각각 X-1로 만들어야 합니다.
DP 정의에 의해, D(s, X-1)에 k+1이 저장되어 있습니다. 결국 D(s, X) = D( D(s, X-1), X-1 )이라는 것을 유도해낼 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
int arr[303030];
int dp[66][303030];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> arr[i];
    for(int i=0; i<66; i++){
        for(int j=1; j<=n; j++){
            if(arr[j] == i) dp[i][j] = j+1;
            else if(!i || !dp[i-1][j] || !dp[i-1][dp[i-1][j]]) dp[i][j] = 0;
            else dp[i][j] = dp[i-1][dp[i-1][j]];
        }
    }

    for(int i=65; i>=0; i--) for(int j=1; j<=n; j++){
        if(dp[i][j]){
            cout << i; return 0;
        }
    }
}