[BOJ] Q1149 RGB 거리

[BOJ] Q1149 RGB 거리

Question

Language: Python

Difficulty: Silver 1

각 집에 대해서는 서로 인접한 집끼리는 색깔이 같아서는 안된다. 색깔이 같지 않은 조건 하에 R,G,B 색깔을 취했을 때 가지는 비용을 최소하면 된다.

			R	G	B
26	40	83	26	40	83
49	60	57	40+49	26+60	26+57
13	89	99	26+57+13	26+57+89	26+60+99

i번째 집이 있다고 가정할때, 만약 i번째 집을 R로 칠하는 경우. 그러면 data[i][Red]+min(data[i-1][Green],data[i-1][Blue]) 만약 i번째 집을 G로 칠하는 경우 그러면 data[i][Green]+min(data[i-1][Red],data[i-1][Blue]) 만약 i번째 집을 B로 칠하는 경우 그러면 data[i][Blue]+min(data[i-1][Red],data[i-1][Green])

이와 같이 구할 수 있다.

각 집별로 RGB 거리를 구해서 맨 마지막 집의 최소 비용을 택하면 된다.

Solution

from math import inf
def solution():
    dp=[[inf] * 3 for _ in range(houses)]
    dp[0]=paint_costs[0]
    for i in range(1,houses):
        dp[i][0]=min(dp[i-1][1],dp[i-1][2]) + paint_costs[i][0]
        dp[i][1]=min(dp[i-1][0],dp[i-1][2]) + paint_costs[i][1]
        dp[i][2]=min(dp[i-1][0],dp[i-1][1]) + paint_costs[i][2]

    return min(dp[houses-1])

if __name__ == "__main__":
    houses=int(input())
    paint_costs=[]
    for _ in range(houses):
        paint_costs.append(list(map(int,input().split())))
    print(solution())