[백준][DP] 1149. RGB거리

1149. RGB거리

 

• 풀이
  • dp로 풀기전 백트래킹 코드 짜보기

n=int(input())
rgb=[list(map(int,input().split())) for _ in range(n)]

answer=float('inf')
def recur(cur,price,prev):
    global answer
    if cur==n:
        answer=min(answer,price)
        return
    
    for i in range(3):
        if i==prev: 
            continue
        recur(cur+1,price+rgb[cur][i],i)

recur(0,0,-1)
print(answer)

 

 

• bottom-up 방식 풀이

n = int(input())
rgb = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
    rgb[i][0] = min(rgb[i-1][1], rgb[i-1][2])+rgb[i][0]
    rgb[i][1] = min(rgb[i-1][0], rgb[i-1][2])+rgb[i][1]
    rgb[i][2] = min(rgb[i-1][0], rgb[i-1][1])+rgb[i][2]

print(min(rgb[n-1]))

 

• top-down 방식 풀이

n=int(input())
rgb=[list(map(int,input().split())) for _ in range(n)]

dp=[[-1]*3 for _ in range(n)]
def recur(cur,prev):
    if cur>n:
        return 746745654635
    if cur==n:
        return 0
    if dp[cur][prev]!=-1:
        return dp[cur][prev]
    
    tmp=float('inf')
    for i in range(3):
        if i==prev: 
            continue
        tmp=min(tmp, recur(cur+1,i)+rgb[cur][i])
    dp[cur][prev]=tmp

    return dp[cur][prev]

print(recur(0,-1))