기록공간

동적계획법을 사용하는 문제였다. 이번 문제는 다른 문제들과 다르게 DP 테이블을 2차원 배열로 만들어줘야 한다. 한 경우(집)에 3가지 값(RGB)을 DP 테이블에 기록해야 하기 때문이다. 예를들어 어떤 집 N을 R로 칠할경우, 전 집 N - 1은 R로 칠할 수 없으므로 G와 B로 칠하는 비용중 가장 작은 비용을 찾아 N의 R로 칠하는 비용을 더해 DP 테이블에 기록하면 된다. N에서 G와 B도 위와 같은 방법으로 해주면 된다. DP(N에서 R) = DP(N - 1에서 G나 B중 가장 작은 값) + H(N에서 R) DP(N에서 G) = DP(N - 1에서 R나 B중 가장 작은 값) + H(N에서 G) DP(N에서 B) = DP(N - 1에서 R나 G중 가장 작은 값) + H(N에서 B) (DP는 DP테이..