1149번 RGB거리(DP)

#문제링크 : https://www.acmicpc.net/problem/1149

n : 집의 갯수
dp : 각 집의 색칠 비용을 담은 2차원 배열
ans : 최소합 비용

전략 : 첫번째 집을 지나, 두번째 집부터 이전 집까지의 색칠 비용의 합 중 더 작은 값을 지금 집의 색칠비용과 더해서 갱신한다. 조건이 이전 집의 색깔과 같으면 안되므로 3가지 경우에 대해 각기 다른 연산을 적용해서 최솟값을 구한다.

※주의사항

1. 큰 문제에서 작은 부분문제를 생각할 때, 그 작은 문제들이 모여 큰 문제의 답이 됨을 인지하자.

Code