[백준`S1] 1149 - RGB거리 (Python)

문제 설명

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

1149번: RGB거리

 

---

문제 풀이

처음에 테이블을 생각할 때 최소비용을 저장하는 1차원 배열로 정의해서 점화식을 생각해봤는데

아무리 생각해도 점화식 구하기 너무 힘들 것 같아서 2차원 배열로 정의했다

 

점화식

d[i][0] = min(d[i - 1][1], d[i - 1][2]) + cost[i][0]
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + cost[i][1]
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + cost[i][2]

 

각 집마다 빨강, 초록, 파랑으로 칠했을 때 비용을 구하기 위해 인덱스를 0, 1, 2로 놓았다

예를 들어 i번째 집을 빨강색으로 칠했을 때 최소 비용(d[i][0])은

i - 1번째 집을 초록으로 칠했을 때의 최소 비용(d[i-1][1]), 파랑으로 칠했을 때의 최소 비용(d[i-1][2]) 중 최솟값과

i번째 집을 빨강으로 칠하는 비용(cost[i][0])을 더해서 구해주었다

 

이렇게 빨강, 초록, 파랑을 모두 구하고 셋 중 최솟값을 출력해주었다

 

n = int(input())
rgb = [list(map(int, input().split())) for _ in range(n)]
d = [[0 for _ in range(3)] for __ in range(n)]

# 초기값 설정
d[0][0] = rgb[0][0]
d[0][1] = rgb[0][1]
d[0][2] = rgb[0][2]

for i in range(1, n):
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + rgb[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + rgb[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + rgb[i][2]

print(min(d[n - 1]))