백준 12026번 BOJ 거리 | python | dp

문제

링크

풀이

먼저 dp는 아래의 사이클을 통해 업데이트 되며
dp 테이블은 n의 크기만큼 1e9로 초기화해준다.

1칸까지 점프하는데 필요한 에너지 양의 최솟값 #실제로 해당 칸은 연산 X
2칸까지 점프하는데 필요한 에너지 양의 최솟값
3칸까지 점프하는데 필요한 에너지 양의 최솟값
...
n칸까지 점프하는데 필요한 에너지 양의 최솟값

예제를 보며 점화식을 구해보자.

9 #링크의 위치
BOJBOJBOJ #보도블럭에 쓰여진 글자

첫 칸은 시작칸이기 때문에 블록의 1번 인덱스부터 (N-1)번 인덱스까지 살펴보면 된다.

2칸까지 점프하는데 필요한 에너지 양의 최솟값
먼저, 2칸까지 점프하는데 필요한 에너지의 최솟값을 구하기 전에
해당 블록을 기준으로 이전에 밟았던 블록은 무조건 고정되어 있다.

def getPrev(x):
    if x == "O":
        return "B"
    elif x == "J":
        return "O"
    elif x == "B":
        return "J"

즉, 2번째칸은 'O'이기에 이전블록은 무조건 'B'여야하므로
뒤에 있는 블록부터 순차적으로 탐색하다가 'B'를 만나는 순간 [해당 블록의 dp값 + 해당 블록에서부터 2번째 칸까지 점프해서 도달하는 에너지의 값을 더한값]과 [원래 해당칸의 dp값] 중 더 작은 값을 골라 갱신해나아가면 된다.

결론적으로 점화식은 다음과 같다

dp[i] = min(dp[i], dp[j] + (j - i) * (j - i))

바로 점화식을 구했기 때문에,
이후 3~9번째칸도 2번째칸까지의 에너지 최솟값을 구하는 것과 완전히 동일하게 진행됨을 바로 파악할 수 있다.

전체코드는 아래와 같다.

import sys

input = sys.stdin.readline

INF = 1e9
n = int(input())
blocks = list(input())
dp = [INF] * n
dp[0] = 0


def getPrev(x):
    if x == "O":
        return "B"
    elif x == "J":
        return "O"
    elif x == "B":
        return "J"


for i in range(1, n):
    for j in range(i):
        prev = getPrev(blocks[i])
        if blocks[j] == prev:
            dp[i] = min(dp[i], dp[j] + (j - i) * (j - i))

# print(dp)

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])