[백준] 12026번 BOJ 거리 구하기 with python

문제 설명

BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다.

스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.

BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다.

스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다.

스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O, J, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구하는 프로그램을 작성하시오.

 

문제 풀이

이 문제는 다이나믹 프로그래밍을 이용하면 쉽게 풀이할 수 있다.

bottom-up 방식을 활용하여 풀면 되고 dp 배열을 만들고 해당 배열은 n+1 만큼의 공간을 할당한다

그리고 dp 배열 활용 방식은 dp 배열의 max로 garbage한 값이 들어가 있고 이 값을 최소값으로 갱신하는 것을 반복해준다. 이 때 for 문을 사용하여 어떤 블럭이 주어졌을 때 블럭 안의 들어있는 단어에 해당하는 index값에 최소의 경우로 접근하는 수를 dp 배열안에 저장해주면 된다. 

 

# boj 거리
# 몇 칸 건너뛸 지에 대한 dp 배열을 만든다

import sys
n=int(sys.stdin.readline())
block=sys.stdin.readline()

# 무조건 pass 해야 되는 경우: B 다음에 O가 나오지 않는 경우
# o가 연속적으로 나오는 경우

dp=[float('inf')]*(n+1)

# B이면 O를 만났을 때 종료, O이면 J를 만날 때까지, J이면 B를 만날 때까지
def get_prev(x):
    if x=='B':
        return 'J'
    elif x=='J':
        return 'O'
    elif x=='O':
        return 'B'
dp[0]=0
for i in range(1,n):
    prev=get_prev(block[i])
    for j in range(i):
        if block[j]==prev: # b다음에 o 식으로 들어왔을 때 
            dp[i]=min(dp[i],dp[j]+pow(i-j,2))

print(dp[n-1] if dp[n-1] !=float('inf') else -1)