[백준/Python] 1149번: RGB 거리

문제

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

 

1149번: RGB거리

코드

n=int(input())
sums=0
d=[]
for i in range(n):
    d.append(list(map(int,input().split())))
for i in range(1,n):
    d[i][0]=min(d[i-1][1],d[i-1][2])+d[i][0]
    d[i][1]=min(d[i-1][0],d[i-1][2])+d[i][1]
    d[i][2]=min(d[i-1][0],d[i-1][1])+d[i][2]

print(min(d[n-1][0],d[n-1][1],d[n-1][2]))

코드설명

2가지를 고려하였다. 열의 크기는 항상 3이기 때문에, 

첫번째는 3가지의 경우로 나눌 수 있는데, 

a)0번째 열 택

b)1번째 열 택

c)3번째 열 택

a의 경우 그 전줄에서 선택지는 1번째, 2번째 열의 최솟값이고,

b의 경우 그 전줄에서 선택지는 0번째, 2번째 열의 최솟값이고,

c의 경우 그 전줄에서 선택지는 0번째, 1번째 열의 최솟값이다.

두번째는 0번행에서 밑에 줄로 내려갈수록 각 줄의 최솟값을 더해가는 것이고,

0번째 행은 그대로 유지하고, 그 밑의 행으로 내려갈 수록 그 전 행의 최솟값과 자신의 행열 값을 더하면 된다.