248 게임( BOJ 12031 )

12031. 248 게임 : https://www.acmicpc.net/problem/12013

12013번: 248 게임

 

문제 파악하기

• 인접한 숫자 중 값이 같은 숫자끼리 합칠 수 있으며, 합치면 그 값보다 1 큰 수 한개로 바꿀 수 있습니다.
• 게임을 진행하면서 만들 수 있는 가장 큰 숫자를 구해야 합니다.
• 인접한 숫자만 합칠 수 있기 때문에 구간에 따른 어떤 값을 구하면 문제를 해결할 수 있을 듯 합니다.

 

문제 해결하기

• 숫자들은 합치는 순서에 따라 만들어지는 최댓값이 달라지기 때문에 효율적인 탐색이 필요합니다.
  이 때, 사용할 수 있는 방법으로는 DP가 있습니다.
• DP[i][j] = 구간 (i ~ j)으로 만들 수 있는 가장 큰 숫자
• 이렇게 DP를 세우면 점화식은 다음과 같습니다.
  DP[i][j] = max( DP[i][j], DP[i][k] + 1 ) ( 단, DP[i][k] = DP[k+1][j] )
• 이렇게 점화식을 세우고 이를 소스코드로 만들면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 250
using namespace std;
 
int N;
int inp[NMAX];
 
int ret;
int dp[NMAX][NMAX];
 
int sv(int s, int e) {
    int a, b, ret;
 
    if(dp[s][e] >= 0) return dp[s][e];
 
    ret = 0;
    for(int k=s;k<e;k++) {
        a = sv(s, k); b = sv(k+1, e);
        if(!a or !b) continue;
 
        if(a == b) ret = max( ret, a+1 );
    }
 
    return dp[s][e] = ret;
}
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d", &inp[i]);
 
    memset(dp, -1, sizeof(dp));
 
    for(int ed=1;ed<=N;ed++) {
        for(int st=N;st>=1;st--) {
 
            if(st == ed) dp[st][ed] = inp[st];
            else dp[st][ed] = sv(st, ed);
 
            ret = max( ret, dp[st][ed] );
 
        }
    }
 
    printf("%d", ret);
 
}

 

후기

재미있는 DP 문제입니다. 어떻게 점화식을 세워야할 지 고민이 조금은 필요하기에 추천하는 문제입니다. 또한, 이 문제는 나올 수 있는 숫자가 64를 넘어가지 않기 때문에 비트 연산자를 사용하면 O(n²)으로도 해결할 수 있으니 도전과제로 남겨둘 필요성이 있다고 생각합니다.