[백준/12026/파이썬] BOJ거리

---

소스코드

n = int(input())

boj = list(input())

big = 99999999

dp = [big]*(n)

dp[0] = 0

def prev_block(x):

  if x == 'B':

    return 'J'

  elif x == 'O':

    return 'B'

  elif x == 'J':

    return 'O'

for i in range(1,n):

  for j in range(i):

    if boj[j] == prev_block(boj[i]):

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

print(dp[n - 1] if dp[n - 1] != big else -1)

---

알고리즘

DP문제입니다. 아직 감이 완전히 잡히지는 않은것 같아요,,ㅜㅡㅜ

이번 문제는 B,O,J 순서대로 가면서 드는 에너지의 양의 최소를 구하는 문제입니다.

그러면 for문 2개를 사용해서 최소값을 갱신해 나가면 되는 문제에요 :)

B,O,J 사이의 거리가 최소인 애들의 에너지양을 갱신하는 DP알고리즘입니다.