나한텐 정말이지 동적 프로그래밍이 어렵다..

백준에서 지금까지 푼 동적프로그래밍 문제중에 내가 풀어서 맞은 문제보다 풀다가 포기하고 답을 본 문제가 더 많다..

하지만 어차피 해야 하는 거라면 될때까지 해야 하는 거니까 시간을 투자해서 최대한 문제를 많이 풀어보자..

https://www.acmicpc.net/problem/1149

예제 입력 1 을 중심으로 내가 문제를 접근한 방식을 정리 한 후 정답 풀이를 정리하겠다.

• Try1
• Try2

지금은 n = 3 (집이 세개) 일 때인데 좀 더 작은 단위인 n = 2일때를 살펴보자

2번째 집을 빨간색으로 칠할 경우 첫 번째 집은 초록색으로 칠했거나 파란색으로 칠해져 있을 경우이다.

2번째 집을 빨간색으로 칠했을 때 가장 작은 비용을 쓰려면 이전 집인 1번째 집을 더 싼 색으로 칠하고 2번째 집을 빨간색으로 칠하는 경우이다. 여기서 1번째집을 칠할 때 더 싼 경우는 초록색으로 칠하는 경우이다.