[Python/Silver1/1149] RGB 거리

|    문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

|    입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

|    출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

 

---

정답 코드

import sys
input = sys.stdin.readline

class Solution:
    def rgb_(self):
        n = int(input())
        home = [list(map(int, input().split())) for _ in range(n)]
        
        for x in range(1,n):
            home[x][0] = min(home[x][0] + home[x-1][1], home[x][0] + home[x-1][2])
            home[x][1] = min(home[x][1] + home[x-1][0], home[x][1] + home[x-1][2])
            home[x][2] = min(home[x][2] + home[x-1][0], home[x][2] + home[x-1][1])
        
        print(min(home[n-1]))
        

if __name__ == "__main__":
    s = Solution()
    s.rgb_()

 

 

|    비고

다이나믹 프로그래밍의 bottom up 방식으로 접근하면 쉽다. 컬러가 3가지밖에 없기 때문에 반복문을 쓰지 않아도 잘 출력된다.