sm 기술 블로그
130. 1149(RGB 거리) 본문
import sys
input = sys.stdin.readline
N = int(input())
housePaintingCost = [list(map(int,input().split())) for _ in range(N)]
for i in range(1, N):
housePaintingCost[i][0] += min(housePaintingCost[i-1][1],housePaintingCost[i-1][2])
housePaintingCost[i][1] += min(housePaintingCost[i-1][0],housePaintingCost[i-1][2])
housePaintingCost[i][2] += min(housePaintingCost[i-1][0],housePaintingCost[i-1][1])
print(min(housePaintingCost[i][0],housePaintingCost[i][1],housePaintingCost[i][2]))
문제요약
각 집을 세가지 색 중에서 가장 저렴한 색으로 칠하여 모든 집을 칠하는데 최소비용을 구하라. (단, N번째 기준 N-1과 N+1집의 색은 같으면 안된다.)
설명
단순히 인덱스가 다르고 그 중에서 최소값을 구하면 되겠구나라고 생각할 수 있다.
그렇다면,
다음과 같을 때 답일 것이다.
하지만
다음과 같이 더 적은 값으로 모든 집을 칠할 수 있다.
따라서 각 케이스 마다 인덱스가 다르고, 최소 값이 아닌 현재 케이스에서 최소값이 아니더라도 다음 케이스에서 작은 값을 더함으로 써 더 낮은 비용이 나올 수 있도록 해야한다.
따라서 누적합을 통해 이를 해결할 수 있다.
housePaintingCost[i][0] += min(housePaintingCost[i-1][1],housePaintingCost[i-1][2])
housePaintingCost[i][1] += min(housePaintingCost[i-1][0],housePaintingCost[i-1][2])
housePaintingCost[i][2] += min(housePaintingCost[i-1][0],housePaintingCost[i-1][1])
현재 케이스의 인덱스와 겹치지 않고 전 케이스의 인덱스에서 작은 값을 더하면서 누적 합을 구해나간다.
min(housePaintingCost[i][0],housePaintingCost[i][1],housePaintingCost[i][2])
세가지의 누적합을 구하게 되는데 그 중 가장 작은 값을 고르면 된다.
'문제 > 백준_파이썬' 카테고리의 다른 글
132. 2579(계단 오르기) (0) | 2022.07.04 |
---|---|
131. 1932(정수 삼각형) (0) | 2022.07.03 |
129. 1912(연속합) (0) | 2022.07.03 |
128. 9461 (파도반 수열) (0) | 2022.07.03 |
127. 1904 (01타일) (0) | 2022.07.03 |
Comments