👉 1149 RGB 거리
[정답 코드]
n = int(input())
house = []
memo = [[0] * 3 for row in range(n)]
for i in range(n):
house.append(list(map(int, input().split())))
if i == 0:
for j in range(3):
memo[0][j] = house[0][j]
for i in range(1, n):
memo[i][0] = min(memo[i - 1][1], memo[i - 1][2]) + house[i][0]
memo[i][1] = min(memo[i - 1][0], memo[i - 1][2]) + house[i][1]
memo[i][2] = min(memo[i - 1][0], memo[i - 1][1]) + house[i][2]
print(min(memo[n - 1]))[풀이]
한 행마다 최솟값을 계속 갱신해나가면서 푸는 동적 프로그래밍 기법을 사용하였다.
1. memo(메모이제이션)의 첫 번째 행에 초기값을 저장한다.
2. 두 번째 행부터 R,G,B(0열, 1열, 2열)을 각각 선택할 때, 그 전 행의 R,G,B 중 조건에 맞는 최솟값(전 집에 어떤 색이 올 때 최솟값인지)을 더하여 memo에 저장한다.
[오류 해결]
처음엔 Brute Force & Backtraking으로 접근하여 쉽게 풀 수 없었다. 질문 검색에서 동적 프로그래밍으로 해결하라는 조언을 보고 계속 생각해보았지만 접근이 잘 안되었다.. 피보나치 문제나, LCS 문제에 사로잡혀 1차원 배열, 2차원 배열만 생각하다보니 R,G,B로 나누어 세 개의 메모이제이션을 진행한다는 것에 접근하기 힘들었던 것 같다.
✔ 동적 프로그래밍은 답을 재활용하는 방식(전에 구했던 답을 이용해 답을 도출하는 것)이라는 기본 원리를 잊지 말자
[적용 자료구조 및 알고리즘]
- Dynamic Programming
