[백준] 12026. BOJ 거리 - Python

[Silver I]

 

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

12026번: BOJ 거리

 

풀이

간단한 DP 문제.

 

맨 마지막 (N번)에서부터 출발하여, 1번까지 필요한 에너지의 양의 최소를 기록하며 나아가면 된다.

 

(dp[i] => (i+1)번부터 N번까지 이동하는 데에 사용하는 에너지의 최솟값)

dp 배열을 생성하여, N번부터 1번까지 모두 순회하며,

현재 위치보다 더 앞쪽에 있는 가능한 위치로의 에너지 최솟값을 기록하자.

 

예를 들어, 아래와 같은 input이 들어왔다고 가정하자.

9
BOJBOJBOJ

우선 dp[8] = 0 이다.

9번(마지막)은 J이고, O -> J 으로 이동해야 하므로,

9번(index 8)로 이동할 수 있던 index는 (O) - 1, 4, 7이다.

따라서, dp[j] = min(dp[j], dp[i] + (i-j)**2) 에 의해,

dp[1] = 49, dp[4] = 16, dp[7] = 1 이 된다.

 

마찬가지로, 8번(index 7)에 의해서도 index 0, 3, 6의 값을 변경-

7번(index 6)에 의해서도 index 2, 5를 변경...~

이 과정을 1번(index 0)까지 반복하게 되면, dp[0]에는 1번부터 N번까지 이동하는 데에 사용하는 에너지의 최솟값이 저장된다.

(만약 1번부터 N번까지 도달하지 못한다면, 값은 INF로 남게 된다.)

 

AC.

N = int(input())
s = list(input())
INF = 10e9
dp = [INF]*N

dp[N-1] = 0
for i in range(N-1, -1, -1):
    for j in range(i-1, -1, -1):
        if s[i] == "B":
            if s[j] == "J":
                dp[j] = min(dp[j], dp[i] + (i-j)**2)
        elif s[i] == "O":
            if s[j] == "B":
                dp[j] = min(dp[j], dp[i] + (i-j)**2)
        elif s[i] == "J":
            if s[j] == "O":
                dp[j] = min(dp[j], dp[i] + (i-j)**2)
                
if dp[0] == INF:
    print(-1)
else:
    print(dp[0])