[Python 3] BOJ - 6988 "타일 밟기"

 # 문제 링크

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

6988번: 타일 밟기

 

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라 생각한다. 상태 공간을 dp[i][j], 현재 i번째 인덱스에서 j번째 인덱스로 타일을 밟을 때 얻을 수 있는 점수의 최대라고 정의한다.

<그림 1. [1,3,5,6,9]의 경우>

 위 그림 1에서 빨간색으로 칠한 두 숫자를 보자. 두 숫자의 차이는 2이며 그 다음에 밟을 타일의 숫자가 5로 정해지게 된다. 위 배열에서 5는 존재하기 때문에 현재 0에서 시작하여 1의 타일을 밟게 된다면 이후에 3개 이상을 밟게 되는 경우임이 자명하기 때문에 1과 3을 더한 4를 채운다.

<그림 2. [1,3,5,6,9]의 경우>

 위 그림 2는 그림 1의 논리에 의해 상태배열의 초기값을 채운 상황이다. dp[0][2]는 0에서 시작하여 2를 밟을때 얻을 수 있는 점수의 최대값인데, 이 때 그 다음에 밟을 타일의 수는 9이고 9는 이미 배열에 있기 때문이다. 같은 논리로 dp[1][3]도 채울 수 있다.

<그림 3. [1,3,5,6,9]의 경우>

 위 그림 3에서의 arr을 보면 1은 초록색, 3은 빨간색, 5는 파란색으로 칠해져 있다. 초록색은 이전 상태의 시작, 빨간색은 이전 상태의 끝이자 현재 상태의 시작, 파란색은 현재 상태의 끝이라고 생각하면 된다. 이미 이전 상태인 dp[초록색][빨간색]은 현재 채워져 있다. 따라서, dp[빨간색][파란색] = max(dp[빨간색][파란색], dp[초록색][빨간색] + arr[파란색의 인덱스])의 점화식이 됨을 알 수 있다. 다만, 점화식을 만족하려면 항상 파란색이 현재 배열에 존재해야 한다.

<그림 4. [1,3,5,6,9]의 경우>

 위 점화식에 따라 현재 1에서 시작하여 5로 끝나고, 그 다음에 9를 밟게 되면 dp[2][4]는 dp[0][2]에서 9를 더한 15가 됨을 알 수 있다.

<그림 5. [1,3,5,6,9]의 경우>

 위 그림 5는 점화식에 의해 채울 수 없는 경우이다. 이전에 dp[0][1]에서 왔으나 7이 없기 때문에 더 이상 타일을 밟을 수 없기 때문에 다른 상태로 전이할 수 없다. 따라서 파란색으로 칠한 숫자가 없다.

<그림 6. [1,3,5,6,9]의 최종 경우>

 위 그림 5는 모든 전이가 끝난 상태를 나타낸다. 현재 dp[3][4]는 dp[1][3]에서 올 수 있으므로 채워 주게 되고, 마지막 dp[3][4]에서는 12가 없기 때문에 상태 전이가 더이상 발생하지 않는다. 따라서 문제의 정답인 18을 구할 수 있다. 이 때 상태 공간의 전체 크기는 $n^2$이기 때문에 시간안에 충분히 정답을 구할 수 있고, 초기에 상태 공간을 채울 때 반드시 3개 이상을 밟는 경우만 초기화가 이루어지므로 아예 타일을 밟을 수 없는 경우에도 문제가 요구하는 정답인 0을 만족한다.

 

 # 코드

import sys

# 입력부
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

# val : 배열의 최대값
val = max(arr)

# check : 현재 숫자가 배열에 존재하지 않으면 -1, 존재하면 그 인덱스를 저장하는 배열
check = [-1] * (val + 1)
for i in range(n):
    check[arr[i]] = i
    
# dp : 현재 i번째 인덱스에서 시작하여 j번째 인덱스를 밟을 때 얻는 최대값을 저장하는 상태 공간
dp = [[0] * n for _ in range(n)]

# 초기화
for i in range(n):
    for j in range(i + 1, n):
        diff = abs(arr[i] - arr[j])
        # 현재 끝나는 지점에서 간격만큼의 수가 있다면 (최소 3개를 밟을 수 있다면) 초기화
        if arr[j] + diff <= val and check[arr[j] + diff] != -1:
            dp[i][j] = arr[i] + arr[j]

# 점화식
for i in range(n - 1):
    for j in range(n):
        # 현재 상태가 가능하다면
        if dp[i][j]:
            diff = abs(arr[i] - arr[j])
            # 그 다음 타일을 밟을 수 있다면 채운다
            if arr[j] + diff <= val and check[arr[j] + diff] != -1:
                dp[j][check[arr[j] + diff]] = max(dp[j][check[arr[j] + diff]], dp[i][j] + arr[check[arr[j] + diff]])

# 정답 출력
ans = 0
for i in dp:
    ans = max(ans, max(i))

print(ans)