[python] 백준 17404 RGB거리2

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

17404번: RGB거리 2

 

문제 해결

R, G, B 3 가지 선택지가 있으므로 dp를 사용할 때 dp[n][0], dp[n][1], dp[n][2] 를 사용해야 할 것 같다.

비욜 cost 리스트를 만들면

dp[n][0] = cost[n][0] + min(dp[n][1], dp[n][2]) 를 사용하면 바로 전에 같은 색을 칠하지 않고 최솟값을 구할 수 있다.

그런데 문제점!

1번 집의 색과 N번 집의 색이 달라야 하는데 이를 어떻게 처리를 할 것인지가 문제이다.

고민을 해봤는데 1번 집에 무슨 색을 칠했는지 정하고 선택 안한 것의 dp값을 maxsize를 놓은 다음 풀어나가고 마지막에 그 색을 선택하지 않는 걸로 하면 될 것 같다.

말로 하면 복잡하니 바로 코드를 보자!

 

import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input())
cost = [[0,0,0]]
ans = INF
for _ in range(n):
    cost.append(list(map(int,input().split())))

for i in range(3): # 1번 집에 무슨 색을 칠할까?
    dp = [[INF, INF, INF] for _ in range(n+1)] # 모두 INF 즉 가장 큰 값을 놓은다음
    dp[1][i] = cost[1][i] # 시작점을 i로 정함으로써 나머지는 maxsize로 놓은다음 밑에 계산에서 min을 시작점 i를 채택하도록 함.
    for j in range(2,n+1):
        dp[j][0] = cost[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = cost[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = cost[j][2] + min(dp[j-1][0], dp[j-1][1])

    for j in range(3): # 마지막 집, 즉 n번 집에 j를 칠한다 할 때
        if i != j: #처음과 마지막이 달라야 하므로
            ans = min(ans, dp[-1][j]) # 최솟값을 구하면 된다.
print(ans)