[백준 13283] Daruma Otoshi

문제 링크 => 13283번: Daruma Otoshi (acmicpc.net)

13283번: Daruma Otoshi

---

다이나믹 프로그래밍 문제이다.

 

약간 이 문제 => 11049번: 행렬 곱셈 순서 (acmicpc.net) 랑 비슷한 느낌인데 재귀로 풀니 계속해서 시간초과를 받았습니다. (왜 그런지는 의문...? ㅠㅠ)

 

그래서 3중 for문으로 해결하였습니다.

 

일단, dp[x][y] 를 [x, y] 범위 내에서 제거할 수 있는 블럭의 수라고 하겠습니다. 

 

풀이는 다음과 같습니다.

 

1. [0, 1], [1, 2], ... , [N-2, N-1] 범위에서 차이가 2 미만인 경우를 블럭을 2개 제거할 수 있으므로 2로 할당합니다. ( dp[x][x+1] = 2 )

 

2. [0, 2], [1, 3], ... , [N-3, N-1] 범위로 격차가 2 이상인 경우 다음을 만족하는 경우를 확인합니다.

• 격차가 짝수인 경우 : 범위 내의 블럭의 수는 홀수입니다. 따라서 다음과 같은 식만 만족하는지를 보면 됩니다.

dp[left][right] = max(dp[left][right], dp[left][k] + dp[k + 1][right]);

• 격차가 홀수인 경우 : 범위 내의 블럭의 수는 짝수입니다. 즉, [left, right] 범위 내에서 left+1 블럭부터 right-1 블럭이 모두 제거되는 경우를 확인한다면 [left, right] 범위 내에서 제거할 수 있는 블럭의 수는 (right - left + 1) 임은 확실합니다.  

if ((right - left) % 2 && dp[left + 1][right - 1] == right - left - 1
&& abs(block[left] - block[right]) < 2) {
	dp[left][right] = dp[left+1][right-1] + 2;
}

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N;
int block[301], dp[301][301];

int solve() {
	for (int gap = 0; gap < N; gap++) {
		for (int left = 0; left < N; left++) {
			int right = left + gap;
			if (right == N) break;
			
			if (gap == 0) {
				dp[left][right] = 0;
			}
			else if (gap == 1) {
				dp[left][right] = (abs(block[left] - block[right]) < 2 ? 2 : 0);
			}
			else {
				for (int k = left; k < right; k++) {
					dp[left][right] = max(dp[left][right], dp[left][k] + dp[k + 1][right]);
					if ((right - left) % 2 && dp[left + 1][right - 1] == right - left - 1
						&& abs(block[left] - block[right]) < 2) {
						dp[left][right] = dp[left + 1][right - 1] + 2;
					}
				}
			}
		}
	}

	return dp[0][N - 1];
}

void initialize() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dp[i][j] = 0;
		}
	}
}

void input() {
	while (1) {
		cin >> N;
		if (N == 0) break;
		initialize();
		for (int i = 0; i < N; i++) cin >> block[i];
		cout << solve() << endl;
	}
}

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

	input();

	return 0;
}