[Python] boj no. 17404 : RGB거리 2

Problem

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

Idea

https://iamyoungbin.github.io/ps/boj-1149/ 에서 제한조건이 추가된 문제이다.

케이스를 집을 칠하는 방법을 색의 수인 세 가지로 나눈다. 각각의 케이스는 첫 번째 집을 어떤 색으로 칠하는가로 분리되며, 각 케이스마다 1149번 문제와 동일한 풀이법으로 구현하되 마지막에 케이스와 같은 색을 칠하는 비용을 제외하고 최소 비용을 구한다.

Code

import sys

input = sys.stdin.readline

N = int(input())
dp = [[0 for _ in range(3)] for _ in range(3)]
cost = [list(map(int, input().split())) for _ in range(N)]
sol = sys.maxsize

for i in range(3):
    idx = 0
    dp[0][0], dp[0][1], dp[0][2] = sys.maxsize, sys.maxsize, sys.maxsize
    dp[0][i] = cost[0][i]
    
    for j in range(1, N):
        pidx = idx
        idx = (idx+1) % 2
        dp[idx][0] = min(dp[pidx][1], dp[pidx][2]) + cost[j][0]
        dp[idx][1] = min(dp[pidx][0], dp[pidx][2]) + cost[j][1]
        dp[idx][2] = min(dp[pidx][0], dp[pidx][1]) + cost[j][2]
       
    sol = min(sol, dp[idx][(i+1)%3], dp[idx][(i+2)%3])
    
print(sol)

Comment