백준 1149 - RGB 거리 (Python3)

코드

n = int(input())

# 별도의 DP 테이블을 생성하지 않음
# RGB 색을 받은 테이블로 처리 가능
rgb = []

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

문제 해설

DP 문제.

문제의 조건을 되게 난잡하게 적어놨는데, 간단하게 요약하자면

i번 집과 i-1번 집의 색을 다르게 칠해야 한다!!!

위와 같다.

이 문제의 경우 색을 칠하는 비용을 입력받는 리스트로 DP 테이블을 대신할 수 있어서 별도의 DP 테이블은 만들지 않았다.

매 집 마다 R, G, B를 선택했을 떄의 값을 이전 집까지 발생한 비용의 누적합(다른 두 색을 고른 경우가 있으므로 총 2가지) 중 최솟값과 이번 집에서 선택한 해당 색을 칠할 때 발생하는 비용을 R, G, B 모든 경우에 따라 고려해주고, 이 중 가장 작은 값을 출력하면 정답이다.