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])

세가지의 누적합을 구하게 되는데 그 중 가장 작은 값을 고르면 된다.