파이썬 백준 12026번: BOJ 거리

문제 

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

12026번: BOJ 거리

 

풀이

i번째 까지 오는데 걸리는 최소 에너지 값을 저장할 DP 테이블 d를 정의한다. 

스타트는 B,O,J 순서로 이동해야하기 때문에 이를 나눠서 계산한다. 

 

예제 입력 4의 동작 방식은 아래와 같다. 

5번째 O의 경우 첫번째 B와의 결과 값이 두번째 B와의 결과값((5-2)*(5-2)+1000001)보다 작으므로 25로 업데이트 된다. 

마찬가지로 6번째, 7번째 o의 dp 테이블 값이 업데이트 된다. 

 

 

8번째 J의 경우 이전에 나왔던 O의 값과 비교하여 업데이트된다. 

8번째 J의 DP table업데이트

 

9번째 J의 DP table업데이트

10번째 J의 DP table업데이트

11번째 J의 DP table업데이트

 

B의 경우 이전에 나왔던 J와 값을 비교하며 업데이트 한다. 

이 값이 마지막이므로 50이 출력된다. 

import sys

N=int(sys.stdin.readline())
road=sys.stdin.readline().strip()
d=[1000001]*len(road)
d[0]=0 #첫번째 값은 0으로 설정 
for i in range(1,len(road)):
    if road[i]=='B': # 글자가 B일때
        for j in range(0,i): # 이전에 나온 J의 값에서 해당 B(road[i])를 선택하는 경우의 최솟값으로 dp테이블 업데이트
            if road[j]=='J':
                d[i]=min(d[i],(i-j)*(i-j)+d[j])
    elif road[i]=='O': # 글자가 O일때
        for j in range(0, i):  # 이전에 나온 B의 값에서 해당 O(road[i])를 선택하는 경우의 최솟값으로 dp테이블 업데이트
            if road[j] == 'B':
                d[i] = min(d[i], (i-j)*(i-j)+d[j])
    else: # 글자가 J일때 
        for j in range(0, i):# 이전에 나온 O의 값에서 해당 J(road[i])를 선택하는 경우의 최솟값으로 dp테이블 업데이트
            if road[j] == 'O':
                d[i] = min(d[i], (i-j)*(i-j)+d[j])

if d[N-1]==1000001:# 끝까지 올수 없을 경우
    print(-1) # -1출력
else:
    print(d[N-1])