[백준] 1149번 - RGB거리 (DP) - 결과 포함

www.acmicpc.net/problem/1149

1149번: RGB거리

이 문제는 처음에 생각했을 때 모든 경우의 수를 고려하는 백트래킹 방법이 떠올랐다.

단순하게 문제에 나온 조건을 그대로 따라가는 것이다.

 

첫 집을 칠할 때는 가장 비용이 적은 색을 선택하고 그 색의 인덱스를 저장한다.

이후에는 그 인덱스에 해당하는 색을 제외하고 다른 색 중에서 더 적은 비용을 가지고 있는 색을 선택한다.

 

하지만 이 방법은 다이나믹 프로그래밍과 맞지 않다고 생각했다.

이 문제를 푼 다른 블로그들을 참고하면서 다이나믹 프로그래밍으로 해결하는 방법을 깨달았다.

 

처음에는 무조건 최솟값을 선택하면 된다.

이후에 모든 경우를 칠해보는 것이다.

즉 내가 지금 빨간색을 칠한다면 이전에 초록색과 파란색 중에서 비용이 적은 색을 선택해서 현재 빨간색의 비용에 더한다.

이 더한 값을 저장해놓는다.

 

이 방식을 이용하면 어떤 색을 골라도 최소 비용으로 색을 선택하게 되고

마지막에 세 개의 결과중에서 가장 최소값을 선택하면 된다.

 

[소스 코드]

n = int(input())
home = []
d = []

for i in range(n):
    home.append(list(map(int, input().split())))

d.append(home[0])

for i in range(1, n):
    d.append([0] * 3)
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + home[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + home[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + home[i][2]

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