[다이나믹 프로그래밍] 백준 1149번: RGB 거리

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

1149번: RGB거리

num = int(input())
lst = []
for i in range(num):
    lst.append(list(map(int, input().split())))

answer =[]
def dfs(a,b,c, idx):
    if idx == num-1:
        answer.append(min(a,b,c))
        return

    cur = lst[idx+1]
    na = min(b+cur[0], c+cur[0])
    nb = min(a+cur[1], c+cur[1])
    nc = min(a+cur[2], b+cur[2])
    dfs(na,nb,nc,idx+1)

init = lst[0]
dfs(init[0],init[1],init[2],0)
print(answer[0])

그동안 풀었던 dp문제들이 기억에 남아있어서

메모이제이션이나 타뷸레이션으로 풀려고 했다. 그러다 도저히 안풀리다가

그래, 무슨 색을 칠할지는 미래에 따라 달라지기 때문에 정할 수 없다. 그렇다면 모든 경우의 수를 따져보자. 

라는 생각이 들었다. 그래서 재귀를 이용하여 a, b, c로 나누어 모든 값을 체크하였다... 좋은 문제!!

 

라고 생각하면서 구글링을 하다가 다이나믹 프로그래밍스러운 풀이를 발견했다.

그래.. 이게 dp지.. 난 아직 멀었다.. 코드 진행 방식은 동일하나 좀 더 dp스럽게 고쳐보았다.

dp값을 세갈래로 나눠서 진행한다는 생각을 아예 하지 못했었는데 이 문제로 배웠다!

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

배운것

- dp의 새로운 유형 발견. dp값을 세 갈래로 나눠서 진행한다는 생각을 배웠다.