BOJ 12008 262144

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/12008

🧐 관찰 및 접근

#

• 흠, 결국 마지막에 사용한 모든 숫자들은 하나의 범위로 나타날 것 같다.
  • 범위를 쪼개는 맛의 DP를 할 수 있나?
    • $\text{DP}[i][j]$: $i$~$j$까지의 숫자를 모두 사용해서 만들어진 수 라고 하면 $O(N^2)$의 시간이 걸린다…
• 이런 느낌으로 $\log$로 바운드 시킬 수 있q을까?
  • $(1, 1, 1, 2)$ 에서 1들을 2로 묶을 수 있는 경우를 각 인덱스에 대해서 표시
  • $(2, 1, 2), (1, 2, 2)$ 등으로 나타내져을때, 2들을 4로 묶을 수 있는 경우에 대해 표시..
  • 그러니까, $(1, 1, 1, 2)$는 2로 묶었을때 다음 인덱스는 $(1, 2, -1, 3)$ 처럼 (0-based)
  • 그러면 뒤로 계속 폴짝폴짝 뛰어다니면서 계산하면, 만들 수 있는 최대값인 58에 대해 $O(N)$번 하면 될거같기도..?

💻 풀이

#

• 코드 (C++):

void solve(){
    int N; cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    vector<vector<int>> v(60, vector<int>(N+1, -1));
    rep(i, 0, N) v[A[i]][i] = i;

    int ans = 0;
    rep(b, 0, 60){
        rep(i, 0, N) if(v[b][i] != -1 && v[b][v[b][i]+1] != -1) v[b+1][i] = v[b][v[b][i]+1];
        rep(i, 0, N) if(v[b][i] != -1) ans = max(ans, b);
    }
    cout << ans;
}