12013 248 게임 (백준, python3)

 

시간 제한	메모리 제한
2초	512MB

문제

Bessie는 큰 손으로 작은 터치스크린을 다루는 것이 불편함에도 불구하고 휴대폰으로 게임을 하는 것을 좋아한다.

그녀는 특히 요즘 하고있는 게임에 흥미를 느끼고 있다. 이 게임은 N개의 양수들(2 ≤ N ≤ 248)로 시작되며, 각 수는 1에서 40 사이이다. 각 수에서 Bessie는 같은 값을 가진 두개의 인접한 수를 그보다 1 큰 수 한개로 바꿀 수 있다. (예를 들어, 그녀는 두 개의 인접한 7을 8로 바꿀 수 있다.) 목표는 수열에서 더이상 합칠 수가 남아있지 않을 때, 즉 게임이 끝났을 때 수열에 있는 가장 큰 수를 최대화 하는 것이다. Bessie가 가능한 가장 높은 점수를 얻을 수 있도록 도와주어라!

 

입력

첫째 줄에는 N을 입력받는다.

2번째 줄부터 N개의 줄에는 게임의 시작에서 주어지는 N개의 숫자를 입력받는다.

 

출력

Bessie가 만들 수 있는 가장 큰 정수를 출력해라.

 

---

풀이

dp[i][j]를 i와 j 구간을 합쳤을 때 얻을 수 있는 가장 큰 점수로 하자. 합치지 못한다면 0을 저장한다. dp[i][i]는 i번째 숫자로 초기화 된다.

 

 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    N = int(input())
    dp = [[0] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = int(input())
    res = 0
    for t in range(1, N):
        for i in range(N - t):
            for k in range(i, i + t):
                if dp[i][k] == dp[k + 1][i + t] > 0:
                    dp[i][i + t] = max(dp[i][i + t], dp[i][k] + 1)
    for i in range(N):
        for j in range(N):
            res = max(dp[i][j], res)
    print(res)
solution()