[python/1149]RGB거리

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

1149번: RGB거리

 

내 코드

규칙 중에서 i-1의 집 색과 i의 집 색이 같으면 안 되고 i+1의 집 색과 i의 집 색이 같으면 안 되기 때문에 i 기준의 식을 세워보아야 한다.

RGB[i][빨간색] = 최솟값(RGB[i-1][초록색], RGB[i-1][파란색]) + RGB[i][빨간색]
RGB[i][초록색] = 최솟값(RGB[i-1][빨간색], RGB[i-1][파란색]) + RGB[i][초록색]
RGB[i][파란색] = 최솟값(RGB[i-1][빨간색], RGB[i-1][초록색]) + RGB[i][파란색]

위와 같은 식을 적용시켜 마지막 값에서 빨간색, 초록색, 파란색 중 최솟값을 찾으면 된다.

 

예를 들어 입력을 아래와 같다고 가정할 때

 

3

1 2 3

3 2 1

1 2 3

 

0번을 1 2 3, 1번을 3 2 1이고 2번을 1 2 3이라고 하면

RGB[1][빨간색] = 최솟값(RGB[0][초록색]:2, RGB[0][파란색]:3) + RGB[1][빨간색]:3
                    = 2 + 3 = 5
RGB[1][초록색] = 최솟값(RGB[0][빨간색]:1, RGB[0][파란색]:3) + RGB[1][초록색]:2
                    = 1 + 2 = 3
RGB[1][파란색] = 최솟값(RGB[0][빨간색]:1, RGB[0][초록색]:2) + RGB[1][파란색]:1
                    = 1 + 1 = 2
0: 1 2 3
1: 5 3 2
2: 1 2 3

RGB[2][빨간색] = 최솟값(RGB[1][초록색]:3, RGB[1][파란색]:2) + RGB[2][빨간색]:1
                    = 2 + 1 = 3
RGB[2][초록색] = 최솟값(RGB[1][빨간색]:5, RGB[1][파란색]:2) + RGB[2][초록색]:2
                    = 2 + 2 = 4
RGB[2][파란색] = 최솟값(RGB[1][빨간색]:5, RGB[1][초록색]:3) + RGB[2][파란색]:3
                    = 3 + 3 = 6
최종 값을 살펴보면
2: 3 4 6
3 = 빨간색(0번) + 파란색(1번) + 빨간색(2번)
4 = 빨간색(0번) + 파란색(1번) + 초록색(2번)
6 = 빨간색(0번) + 초록색(1번) + 파란색(2번)

으로 이중 가장 작은 값은 3이다.

 

코드를 작성하면 아래와 같다.

if __name__ == '__main__':
    N = int(input())
    RGB = []
 
    for i in range(N):
        RGB.append(list(map(int, input().split())))
 
    for j in range(1, len(RGB)):
        RGB[j][0] = min(RGB[j - 1][1], RGB[j - 1][2]) + RGB[j][0]
        RGB[j][1] = min(RGB[j - 1][0], RGB[j - 1][2]) + RGB[j][1]
        RGB[j][2] = min(RGB[j - 1][0], RGB[j - 1][1]) + RGB[j][2]
    print(min(RGB[-1][0], RGB[-1][1], RGB[-1][2]))