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

문제 요구사항

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

문제 풀이

• 탑 다운 방식의 dp풀이
• 점화식: d[n] = min(d[n] + d[n-i] + (n-i)**2), (i = 0 .. n-1)

def dfs(i, boj_idx):
    if i == 0:
        if boj[boj_idx] == "B":
            return 0
        else:
            return INF

    if d[i] < INF: return d[i]

    next_boj_idx = (boj_idx-1) % 3
    for j in range(i-1, -1, -1):
        if arr[j] == boj[next_boj_idx]:
            d[i] = min(d[i], dfs(j, next_boj_idx)+(i-j)**2)

            
n = int(input())
arr = list(input())
d = [-1] * n
boj = "BOJ"
LINK = boj.index(arr[-1]) # LINK가 어떤 블록에 서있는지 

#  Top-down방식
ans = dfs(n-1, LINK)
print(ans if ans < INF else -1)