[BOJ/백준] 12026번 BOJ 거리 (Python 파이썬)

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

12026번: BOJ 거리

 

문제

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, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.

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

입력

첫째 줄에 1 ≤ N ≤ 1,000이 주어진다.

둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.

출력

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.

예제 입력 1 

9
BOJBOJBOJ

예제 출력 1 

8

예제 입력 2 

9
BOJBOJBOJ

예제 출력 2 

8

예제 입력 3 

8
BJJOOOBB

예제 출력 3 

-1

예제 입력 4 

13
BJBBJOOOJJJJB

예제 출력 4 

50

예제 입력 5 

2
BO

예제 출력 5 

1

예제 입력 6 

15
BJBOJOJOOJOBOOO

예제 출력 6 

52

 

---

풀이

문제를 살펴보면, 점프를 뛰어서 N번째에 도달할 수 있는지 확인하는 문제입니다. 이때 점프는 아래 3가지만 허용됩니다.

B -> O,  O -> J,  J -> B

만약 도달에 성공한다면, 그때 점프를 하는데 필요한 에너지 양의 최솟값을 출력해야 하며, 불가능하면 -1 출력해야 합니다.

우선, 주어진 블록들을 받은 후, i번째 블록에 도달할 때 필요한 최소한의 에너지 양을 담을 dp을 선언하였습니다.

blocks = list(input().rstrip())
dp = list(1e9 for _ in range(N))
dp[0] = 0

 

첫칸은 'B'로 고정이니, 1번 인덱스부터 N까지 탐색하여 각각 점프가 가능한지, 가능하다면 최솟값은 어떻게 되는지를 구해야 합니다.

우선 각 블록마다 점프가 가능한 경우의 수는 아래와 같이 표현할 수 있습니다.

    check_jump = '?'

    if block == 'B':
        check_jump = 'J'
    elif block == 'O':
        check_jump = 'B'
    else:
        check_jump = 'O'

이제, 뒤에 있는 블록들로 부터 해당 블록까지 점프해서 도달할 때, 에너지의 최솟값을 저장해야 합니다.

점프할 때는 점프 거리의 제곱만큼 에너지가 소모되므로 아래와 같이 작성합니다.

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

 

이때, 도달 불가능 여부를 확인하기 위해서 dp을 아래와 같이 수정하겠습니다. 

visited = True
dp = list([1e9, not visited] for _ in range(N))
dp[0][0], dp[0][1] = 0, True

이제, 마지막 블록에서 visited가 False라면 도달하지 못한 것이므로 -1을 출력하도록 코드를 작성합니다.

 

for i in range(1, N):
    block = blocks[i]
    check_jump = '?'

    if block == 'B':
        check_jump = 'J'
    elif block == 'O':
        check_jump = 'B'
    else:
        check_jump = 'O'

    for j in range(i):
        if check_jump == blocks[j]:
            # j -> i로 점프
            dp[i][0] = min(dp[i][0], dp[j][0] + pow(i-j, 2))

            if dp[i][0] != 1e9:
                dp[i][1] = True

 

최종적인 구현은 아래와 같습니다.

 

Code

# k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k
import sys
input = sys.stdin.readline
N = int(input())
blocks = list(input().rstrip())
visited = True
dp = list([1e9, not visited] for _ in range(N))
dp[0][0], dp[0][1] = 0, True


for i in range(1, N):
    block = blocks[i]
    check_jump = '?'

    if block == 'B':
        check_jump = 'J'
    elif block == 'O':
        check_jump = 'B'
    else:
        check_jump = 'O'

    for j in range(i):
        if check_jump == blocks[j]:
            # j -> i로 점프
            dp[i][0] = min(dp[i][0], dp[j][0] + pow(i-j, 2))

            if dp[i][0] != 1e9:
                dp[i][1] = True

if dp[N-1][1]:
    print(dp[N-1][0])
else:
    print(-1)