백준12013 248 게임

작성일 | In

문제 링크

  • http://icpc.me/12013

문제 출처

  • US Open 2016 Gold 3번

사용 알고리즘

  • 구간 DP

시간복잡도

  • O(N3)

풀이

dp[i][j] = [i, j]구간에서 만들 수 있는 유일한 정수 중 최댓값

유일한 정수라는 것은 숫자들을 합쳐서 남는 단 한 개의 정수를 의미합니다.
만약 한 개의 정수를 남기지 못한다면 0으로 합니다.

dp[i][i] = arr[i]인 것은 자명합니다.
dp[i][k]와 dp[k+1][j]가 같은 경우, 다시 말해 인접한 두 구간이 만들 수 있는 유일한 정수가 같다면 dp[i][j] = dp[i][k] + 1이 됩니다.
세제곱 dp를 돌려주면 됩니다.

전체 코드

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
28
29
#include <bits/stdc++.h>
using namespace std;

int arr[333];
int dp[333][333];
int ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> arr[i]; dp[i][i] = arr[i];
		ans = max(ans, arr[i]);
	}

	for (int sz = 1; sz <= n; sz++){
		for (int i = 1; i <= n; i++){
			int j = i + sz; if (j > n) break;
			for (int k = i; k < j; k++){
				if (dp[i][k] == dp[k + 1][j]){
					dp[i][j] = max(dp[i][j], dp[i][k] + 1);
				}
				ans = max(ans, dp[i][j]);
			}
		}
	}

	cout << ans;
}