[알고리즘/파이썬] 백준 17404 - RGB거리 2

문제

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

17404번: RGB거리 2

 

 

풀이

RGB거리1 문제와는 다른 조건이 하나 더 걸려있다. 바로 1번 집과 마지막 집의 색이 동일하면 안 된다는 점.

 

따라서

1. 1번 집을 R로 색칠하고 N번집을 G 또는 B로 칠한 경우

2. 1번 집을 G로 색칠하고 N번 집을 R 또는 B로 칠한 경우

3. 1번 집을 B로 색칠하고 N번집을 R 또는 G로 칠한 경우

각 세계의 경우에 따라 dp를 수행하고 각 경우에 최소값 중 작은 값을 찾아 결과로 도출한다.

 

코드

import sys
R, G, B = 0, 1, 2

N = int(sys.stdin.readline().rstrip())
cost = []
for _ in range(N):
    cost.append(list(map(int, sys.stdin.readline().rstrip().split())))

answer = 1e9
for c in range(3):
    dp = [[-1]*3 for _ in range(N)]

    dp[0] = [1001, 1001, 1001]
    dp[0][c] = cost[0][c]

    for i in range(1, N):
        dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + cost[i][R]
        dp[i][G] = min(dp[i-1][R], dp[i-1][B]) + cost[i][G]
        dp[i][B] = min(dp[i-1][R], dp[i-1][G]) + cost[i][B]
    dp[N-1][c] = 1e9
    answer = min(answer, min(dp[N-1]))
    
print(answer)