17404_RGB거리2

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

17404번: RGB거리 2

 

 

RGB거리 문제와 동일하지만 첫번째 집과 마지막집이 연결된 형태이다. 

 

첫집과 마지막집의 색이 같아야 하지 않으므로 세 경우를 집어서 생각할 수 있다.

 

첫집을 R로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 G,B로 칠한것중 최소비용

첫집을 G로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 R,B로 칠한것중 최소비용

첫집을 B로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 R,G로 칠한것중 최소비용 

 

 

이걸 구현하기 위해서 3번 비용을 계산하는데, 첫집의 비용을 R로 잡았다고 치면 G,B를 칠할 비용을 엄청 크게 잡아서 선택되지 않게 하였다.

 

마찬가지로 마지막에 최소비용을 구할때도 같은 방식을 사용하였다.

import sys
input = sys.stdin.readline

n = int(input())
cost = [ list(map(int,input().split())) for _ in range(n)]
result = []
for i in range(3):
    dp = [ [0,0,0] for _ in range(n) ]
    dp[0] = [1e9,1e9,1e9]
    dp[0][i] = cost[0][i]
    for j in range(1,n):
        dp[j][0] = min(dp[j - 1][1], dp[j - 1][2]) + cost[j][0]
        dp[j][1] = min(dp[j - 1][0], dp[j - 1][2]) + cost[j][1]
        dp[j][2] = min(dp[j - 1][0], dp[j - 1][1]) + cost[j][2]

    dp[-1][i] = 1e9
    result.append(min(dp[-1]))
print(min(result))