[백준 12013] 248 게임

문제 링크 : 12013번: 248 게임 (acmicpc.net)

12013번: 248 게임

 

Bessie 는 두 개의 인접한 수가 같을 때 (인접한 수 + 1) 로 합칠 수 있다고 한다.

즉 이러한 작업을 계속 하여 더이상 진행이 되지 않도록 하는 수열에 대해서 가장 큰 수를 구하는 문제이다.

위 문제를 다이나믹 프로그래밍으로 \(O(N^{3})\) 시간복잡도로 해결했다.

 

 

※ 접근 방법

1. dp[l][r] 을 [l, r] 범위 내에 얻을 수 있는 최대 점수라고 설정하였다.

    그렇다면 자연스럽게 기본 케이스는 다음과 같이 가져갈 수 있다.

	/* 1. base case */
	for (int i = 1; i <= N; i++) {
		dp[i][i] = A[i];
	}

 

2. [l, r] 범위에서 r - l > 1 일 때 어떻게 optimal substructure 를 구상할 것인지에 대한 고민이 필요했다.

    즉, 이전의 memoziation 으로 설정된 기본 케이스를 가지고 이어가야 한다.

    그러면 문제에서 주어진 수열 [1, 1, 1, 2] 를 가지고 규칙을 찾아본다.

 

• dp[1][2] = 2 : dp[1][1] == dp[2][2]  ~>  (dp[1][1] + 1) = 2 
• dp[3][4] = 2 : dp[3][3] != dp[4][4]  ~>  max(dp[3][3], dp[4][4]) = 2 
• dp[1][3] = 2 : dp[1][1] != dp[2][3], dp[1][2] != dp[3][3]  ~>  max(max(dp[1][1], dp[2][3]), max(dp[1][2], dp[3][3])) = 2
• dp[2][4] = 3 : dp[2][3] == dp[4][4]  ~>  (dp[2][3] + 1) = 3

 

정리하자면, 위와 같은 순서로 memoziation 을 비교하면서 같을 경우와 다를 경우에 대한 식을 구할 수 있다.

 

\( dp[l][r]_{l \leq k \leq r-1} 
= \begin{cases}
 dp[l][k] + 1 & \text{if dp[l][k] = dp[k+1][r]}  \\
 max(dp[l][k], dp[k+1][r]) & \text{if dp[l][k] != dp[k+1][r]}  
\end{cases} \)

 

이렇게 설계를 하고 코드 구현을 한 다음에 기분좋게 제출을 한 결과 틀렸다.

 

 

그렇다. 

고려해야 할 게 더 있다.

 

3. 수열 [1, 2, 1, 2] 를 2 번에서 설계된 구조를 가지고 구해보도록 하자.

 

• dp[1][2] = dp[2][3] = dp[3][4] = 2 
• dp[1][3] = 2 : dp[1][1] != dp[2][3], dp[1][2] != dp[3][3]  ~>  max(max(dp[1][1], dp[2][3]), max(dp[1][2], dp[3][3])) = 2
• dp[2][4] = 3 : dp[2][2] != dp[3][4], dp[2][3] != dp[4][4]  ~> max(max(dp[2][2], dp[3][4]), max(dp[2][3], dp[4][4])) = 3

 

dp[2][4] 의 값이 잘못된 것을 알 수 있다.

즉, max(dp[2][2], dp[3][4]) 에서 dp[3][4] 가 2 인것은 맞지만 합쳐져서 2 가 된 것인지 아닌지에 대한 정보가 없다.

따라서 2차원 배열을 하나 더 선언하였다. 

check[l][r] = [l, r] 범위 내에 합쳐진 결과인지에 대한 정보 (true/false)

 

 

위와 같이 check 배열을 추가 선언하여 해결할 수 있다.

 

풀이 코드

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <set>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N;
int A[250];
int dp[250][250];
bool check[250][250];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> A[i];
}

void solution() {
	int r;

	/* 1. base case */
	for (int i = 1; i <= N; i++) {
		dp[i][i] = A[i];
		check[i][i] = true;
	}

	/* 2. dynamic programming */
	for (int gap = 1; gap <= N - 1; gap++) {
		for (int l = 1; l <= N - gap; l++) {
			r = l + gap;
			for (int k = 0; k <= gap - 1; k++) {
				if (dp[l][l + k] == dp[l + k + 1][r]
					&& check[l][l + k] && check[l + k + 1][r]) {
					dp[l][r] = max(dp[l][r], dp[l][l + k] + 1);
					check[l][r] = true;
				}
				else dp[l][r] = max(dp[l][r], max(dp[l][l + k], dp[l + k + 1][r]));
			}
		}
	}

	/* 3. Find solution */
	cout << dp[1][N];
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution();

	return 0;
}