March 9, 2023

문제 요약

• N개의 블럭은 B, O 또는 J로 이루어져있고, 1번에서 시작하여 N번으로 이동
• 블럭 간 점프가 가능한데 점프 시 칸수 차이의 제곱만큼의 에너지가 필요
• 최소 에너지 출력
• 각 이전 알파벳으로부터만 점프가 가능
• 1 ≤ N ≤ 1,000

풀이

from sys import maxsize

N = int(input())
board = list(input())
dp = [maxsize] * N

dp[0] = 0

for i in range(N):
    now_char = board[i]
    for j in range(i):
        prev_char = ''

        if (now_char == 'B'):
            prev_char = 'J'
        elif (now_char == 'O'):
            prev_char = 'B'
        else:
            prev_char = 'O'

        if (dp[j] != maxsize and board[j] == prev_char):
            dp[i] = min(dp[i], dp[j] + (i - j) ** 2)

print(dp[N - 1] if dp[N - 1] != maxsize else -1)

• i번째 까지의 최소 에너지를 기록