백준 12026 파이썬 python : BOJ 거리 @@황소처럼 우직하게@@ 시간초과 포비아 쉣더퍽

포비아포비아!

n = int(input())
lst = input()

ans = 999999999
def go(idx, cost):
    global ans
    if idx == n - 1:
        ans = min(ans, cost)
        return
    now = lst[idx]
    if now == 'B':
        for i in range(idx + 1, n):
            if lst[i] == 'O':
                go(i, cost + pow(i - idx, 2))
    elif now == 'O':
        for i in range(idx + 1, n):
            if lst[i] == 'J':
                go(i, cost + pow(i - idx, 2))
    elif now == 'J':
        for i in range(idx + 1, n):
            if lst[i] == 'B':
                go(i, cost + pow(i - idx, 2))
go(0, 0)
print(ans if ans != 999999999 else -1)

위와 같이 짜면 시간초과.

재귀에 이어서 또 엄청난 재귀가 이어지지..

특정 인덱스에 가는 방법이 매우 여러가지야

반면, 아래와 같은 반복문은 간단하지

n * n 의 시간복잡도 1,000,000 작은 숫자지.

n = int(input())
lst = input()

MAX = 999999999
dp = [MAX] * n

def get_prev(x):
    if x == "B":
        return "J"
    elif x == "O":
        return "B"
    elif x == "J":
        return "O"

dp[0] = 0
for i in range(1, n):
    prev = get_prev(lst[i])
    for j in range(i):
        if lst[j] == prev:
            dp[i] = min(dp[i], dp[j] + pow(i - j, 2))
print(dp[n - 1] if dp[n - 1] != MAX else -1)