[Python] 백준 12026번: BOJ 거리

# 문제 내용

백준 12026번: BOJ 거리

12026번: BOJ 거리

 

# 알고리즘 분류

• 다이나믹 프로그래밍

 

# 풀이

import sys
input = sys.stdin.readline
INF = sys.maxsize

# 보도블럭 길이 1~n까지, 목적지는 n
n = int(input())

# 보도블럭
data = list(input())

# B->O->J 순으로 밟아야하며
# k칸 점프하는데 필요한 에너지 양은 k*k
dp = [INF] * n
dp[0] = 0

for i in range(1, n):
  for j in range(i):
    if data[j] == 'B' and data[i] != 'O':
       continue
    elif data[j] == 'O' and data[i] != 'J':
      continue
    elif data[j] == 'J' and data[i] != 'B':
      continue
    dp[i] = min(dp[i], dp[j] + pow(i-j, 2))


if dp[n-1] == INF:
  print(-1)
else:
  print(dp[n-1])