백준: 1149 RGB 거리

문제

1149번: RGB거리

 

문제 풀이

 메모이제이션을 잘 활용하면, 어렵지 않게 풀 수 있다. 또한 각 N행은 하나의 집을 나타내고 1, 2, 3열은 R, G, B로 칠 할 경우 발생하는 비용을 의미한다.

 

 기본 예제는 그림과 같이 나타낼 수 있다. 집 1(0번 인덱스)은 첫 번째 집이기에 값을 누적시킬 필요가 없다. 따라서 집 2(1번 인덱스)부터는 해당 색상을 선택하였을 때, 이전의 집에서 선택할 수 있는 색상의 값 중 최솟값을 더한다. 이를 통해 집 2에 합산한 값은 값은 89, 86, 83가 된다. 마찬가지로 집 3의 경우도 이 과정을 거치면 96, 172, 185라는 값을 얻을 수 있다. 따라서 해당 예시에서는 집 1, 2, 3은 각각 빨강, 파랑, 빨강으로 선택하였을 때 최솟값으로 칠할 수있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    R, G, B = 0, 1, 2
    n = int(stdin.readline())

    prices = \
        [list(map(int, stdin.readline().split())) for _ in range(n)]

    for i in range(1, n):
        prices[i][R] += min(prices[i - 1][G], prices[i - 1][B])
        prices[i][G] += min(prices[i - 1][R], prices[i - 1][B])
        prices[i][B] += min(prices[i - 1][R], prices[i - 1][G])

    print(min(prices[-1]))