[Python] 백준 1149번 RGB거리

문제

1149번: RGB거리

입력

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

출력

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

입력 예제

3
26 40 83
49 60 57
13 89 99

3
1 100 100
100 1 100
100 100 1

출력 예제

96

3

문제 풀이

• 각 집의 색을 칠할 때의 조건에 따라 앞에 있는 집과 뒤에 있는 집의 색은 같을 수 없다,
• 따라서 모든 집에 빨간색, 초록색, 파란색을 하나씩 칠해보면서 최솟값을 구하여 각 집에 색을 칠한다.
• 따라서 점화식은 아래와 같다.

# 현재 집의 값을 빨간색으로 칠하는 최솟값
color[i][0] += min(color[i - 1][1], color[i - 1][2])
# 현재 집의 값을 초록색으로 칠하는 최솟값
color[i][1] += min(color[i - 1][0], color[i - 1][2])
# 현재 집의 값을 파란색으로 칠하는 최솟값
color[i][2] += min(color[i - 1][0], color[i - 1][1])

• 마지막 집까지 색칠한 후 최솟값을 출력하면 최소한의 비용으로 모든 집을 칠하는 값을 구할 수 있다.

코드

n = int(input())
color = []
for i in range(n):
    color.append(list(map(int,input().split())))

# 각 집을 빨초파로 칠한 최솟값을 구해서 넣기
# 앞 뒤 집의 색이 같으면 안되므로 색이 중복되지 않도록 확인
for i in range(1, n):
    # 현재 집의 값을 빨간색으로 칠했을 때의 값
    color[i][0] += min(color[i - 1][1], color[i - 1][2])
    # 현재 집의 값을 초록색으로 칠했을 때의 값
    color[i][1] += min(color[i - 1][0], color[i - 1][2])
    # 현재 집의 값을 파란색으로 칠했을 때의 값
    color[i][2] += min(color[i - 1][0], color[i - 1][1])

# color[n - 1][i]번지의 최솟값 출력
print(min(color[n - 1]))