[BOJ] 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을 출력한다.

풀이

웹 프로그래밍 수업을 시작하기 전 워밍업 겸으로 문제 하나를 풀었다. N의 범위를 확인한 후 브루트포스로 풀면 당연히 TLE가 나올것이기 때문에 각 문자에 오기 위해 드는 최소의 비용을 DP 배열에 저장하는 방법을 생각하였다. 문제에서 주어진 조건으로 인하여 우리는 B, O, J 순으로 이동을 해야하기 때문에 조건문을 통하여 B일 때는 O로, O일 때는 J로, J일때는 B로 이동하게 하였고, 드는 비용을 현재 dp에 저장되어 있는 값과 비교하여 더 작은 값을 저장하였고, DP 배열의 초기값은 1e9로 무한대 값 대신해서 넣어주었다. 만약 모든 과정이 끝난 후 링크가 있는 자리(dp[n-1])이 1e9면 갈 수 있는 방법이 없는 것이므로 -1을 출력하였고, 그게 아니면 dp[n-1]을 출력하였다.

import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
S = input()
dp = [1e9] * n
dp[0] = 0
for i in range(n-1):
  for j in range(i+1, n):
    if S[i] == 'B':
      if S[j] == 'O':
        dp[j] = min(dp[j], dp[i] + (j-i)**2)
    if S[i] == 'O':
      if S[j] == 'J':
        dp[j] = min(dp[j], dp[i] + (j-i)**2)
    if S[i] == 'J':
      if S[j] == 'B':
        dp[j] = min(dp[j], dp[i] + (j-i)**2)
if dp[n-1] == 1e9:
  print(-1)
else:
  print(dp[n-1])