BOJ 12013 - 248게임 (dp)

https://www.acmicpc.net/problem/12013

dp[i][j] : 구간[i,j]~~

 

<문제설명>

40이하의 자연수가 최대 248개 주어진다. 인접한 두 수가 같다면 1을 더한 값으로 합칠 수 있다. (7,7,1->8,1)

더이상 합칠 수 없을 때까지 합친 후에 남아있는 수 중 가장 큰 수의 최대값을 구해라.

 

<풀이>

dp[i][j] : i~j를 합할때 남아있는 수 중 가장 큰 수.

dp[i][i]=a[i]

dp[i][j] =if(dp[i][k]==dp[k+1][j])  max ( dp[i][k]+1; )

i~j간격 1부터 차례로 갱신해야 하는 것에 주의. for문의 가장 바깥에 해당하는 것이 간격임. (코드의 sz)

 

모든 d중 최대값이 정답

 

<코드>

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <utility>
#include <tuple>
#include <functional>
#include <cmath>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MAX = 248;

int main() {
	FAST;
	int n, d[MAX][MAX]{ 0 }, ans=0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> d[i][i];
		ans = max(ans, d[i][i]);
	}
	
	for (int sz = 1; sz < n; sz++) {
		for (int i = 0; i + sz < n; i++) {
			for (int k = i; k < i+sz; k++) {
				if (d[i][k] == d[k + 1][i + sz])
					d[i][i + sz] = max(d[i][i + sz], d[i][k] + 1);
				ans = max(ans, d[i][i + sz]);
			}
		}
	}

	cout << ans << '\n';
}

 

 

<생각>

솔루션 찾아봤던 문제