[백준 12026번] 파이썬 - BOJ 거리

백준 12026 - BOJ 거리

시간 제한 2초, 메모리 제한 512MB

# 조건

• 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을 출력한다.

# 접근 방법

• 다이나믹 프로그래밍을 이용하여 풀어주면 된다.
• 시작은 무조건 B이고 B, O, J 순으로만 이동가능하다.
• N 크기의 dp 배열을 최댓값으로 만들어주고, 0번 인덱스를 0으로 초기화해준다.
• 주어진 배열을 순회하면서, 현재 블록에서 점프할 수 있는 블록을 기록해주고 (B면 O)
  • 시작이 N-1부터, i까지 순회하는 반복문을 돌려준다.
  • 현재 블록에서 점프 가능한 블록이라면 dp를 갱신해준다.
    • dp[j] = min(dp[j], dp[i] + (j-i)^2)
• dp[-1] 값이 최댓값이라면 -1 출력, 그렇지 않다면 값을 출력해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
blocks = list(input().rstrip())  
dp = [0] + [float('inf')] * (N-1)  
path = ['B', 'O', 'J']  


for i, val in enumerate(blocks):  
    now = path.index(val)  
    n_val = path[(now+1)%3]  
    for j in range(N-1, i, -1):  
        if blocks[j] == n_val:  
            dp[j] = min(dp[j], dp[i] + (j-i)**2)  

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