(Python) - BOJ(1149번) : RGB거리

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

1149번: RGB거리

---

• 해설 : 

 N개의 집이 있고 집을 색칠하는데 드는 비용이 R, G, B 색깔별로 주어진다. 이 집을 R, G, B의 색들 중 하나로 색칠하려 할 때, 인접하는 집 끼리는 색이 같지 않게 색칠하는 방법 중 비용이 가장 적게 드는 경우의 비용을 찾는 문제이다.

 

 

 

---

• 풀이 :

DP문제이다. 0번째 집부터 각 집마다 색칠하는데 드는 총 비용중 최솟값만을 갱신하며 계산한다.

핵심은 인접한 집끼리는 색이 같으면 안된다는 것이다. 

 

0번째 : R,

1번째 : G,

2번째 : B 

 

로 주어질 때, index에 +1과 +2를 한 값의 mod(3) 값이 다른 색을 선택하는 경우이므로 

현재 값 + min(index+1의 색 코스트, index+2의 색 코스트)로 갱신해주면 된다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
 
if __name__ == "__main__":
    N = int(input())
    cost = []
    for _ in range(N):
        cost.append(list(map(int,input().split())))
    dp = [[] for _ in range(N+1)]
    dp[1] = cost[0]
    for i in range(2,N+1):
        for j in range(3):
            dp[i].append(cost[i-1][j]+min(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]))
    print(min(dp[N]))