[다이나믹 프로그래밍] 백준 17404번: RGB거리 2 / 골드 4**

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

17404번: RGB거리 2

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0, 0, 0] for _ in range(n)]
colors = [[0, 0, 0] for _ in range(n)]
for i in range(n):
    colors[i] = list(map(int, input().split()))

dp[0] = colors[0]

result = []

def compute():
    for i in range(2, n):
        r, g, b = colors[i]
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b


# start is g or b / finish is r
dp[1][0] = min(dp[0][1], dp[0][2]) + colors[1][0]
dp[1][1] = dp[0][2] + colors[1][1]
dp[1][2] = dp[0][1] + colors[1][2]
compute()
result.append(dp[-1][0])

# start is r or b / finish is g
dp[1][0] = dp[0][2] + colors[1][0]
dp[1][1] = min(dp[0][0], dp[0][2]) + colors[1][1]
dp[1][2] = dp[0][0] + colors[1][2]
compute()
result.append(dp[-1][1])

# start is r or g / finish is b
dp[1][0] = dp[0][1] + colors[1][0]
dp[1][1] = dp[0][0] + colors[1][1]
dp[1][2] = min(dp[0][0], dp[0][1]) + colors[1][2]
compute()
result.append(dp[-1][2])

print(min(result))

조금 어렵게 푼 감이 있어 다른 사람 풀이를 참고하니 

역시나 쉽게 접근하여 푸는 방법이 있었다. 

 

내 풀이와 다른 점은 나는 끝 지점을 고정하고 출발점을 제한 하였다.

예를 들어 끝점이 r일 경우를 고정하고, 출발 점이 g 또는 b인 경우를 확인 하였다. 

그래서 코드도 보다시피 하나의 반복문에 넣을 수가 없어서 비슷한 형태의 코드가 세 번 반복되는 걸 볼 수 있다.

 

그런데 고수님들의 풀이는 시작점을 고정했다. 

사실 이 생각도 했지만 시작점을 dp에서 도대체 어떻게 정하냐 라는 생각에 더 이상 생각의 확장을 하지 못했었는데

첫번째 집에서 r을 시작점으로 고정하려면 g, b 값을 무한대값으로 줘버리면 되는 것이었다. ...!! 

생각보다 간단한 작업이라 현타가 왔다.