1149 RGB거리

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline
N = int(read())
graph = [ list(map(int,read().split())) for _ in range(N)]
dp_table =[[0 for _ in range(3)] for __ in range(N)] # N번째 집마다 RGB의 값들을 표현하자. 즉, NX3의 모습을

dp_table[0] = graph[0]
for i in range(1,N):
    dp_table[i][0] = min(dp_table[i-1][1], dp_table[i-1][2]) + graph[i][0]
    dp_table[i][1] = min(dp_table[i-1][0], dp_table[i-1][2]) + graph[i][1]
    dp_table[i][2] = min(dp_table[i-1][0], dp_table[i-1][1]) + graph[i][2]

print(min(dp_table[-1]))

3. 문제 풀이

일단 최솟값, 최댓값을 구하는 문제는 DP를 의심해봐야한다. 그리고 가장 중요한 것은 bottom up으로 진행할 때, 첫 단추부터 잘 꿰서 가지를 계속 이어나간다는 느낌으로 재귀형식을 풀어나가야 한다는 것을 잊지말자.

예를 들면, 집을 R,G,B로 색칠해야한다고 하고, dp_table[0]의 1번째 칠하기를 각각의 색으로 칠한다고 해보자. 왜냐하면, 셋 중에 어떤걸 선택해야 최솟값의 시작점이 될지 모르기 때문에 3개의 경우를 전부 구해야 한다.

그럼 dp_table[1]에서 2번째 칠하기를 하려면, 예를 들어 2번째 집을 R로 칠한다면, 1번째 집은 조건에 의해 G,B 로밖에 칠할 수 없다. 그렇다면 dp_table[0]에서 G,B의 값 중 작은 것을 선택하여 2번째 집에서 R로 칠하는 비용과 더해주면 되는 것이다.

오.. 설명을 적고나니까 이런 생각이 되게 중요한 것 같다. 예를 들어 2번째 집을 R로 칠한다면, 1번째 집은 조건에 의해 G,B 로밖에 칠할 수 없다. 이게 되게 직관적인 느낌이다. 만약 i번째의 값이 이렇다면, i-1번째의 어떤걸 가져다 써야할까? 가 bottom up의 가장 기본적인 생각인 것 같다.