개어렵네

백준 1149 풀이 (다이나믹 프로그래밍)

상당히 헤맸던 문제였다. 역시 더 열심히 해야겠다. 처음에는 R,G,B중에 하나를 정하고 이후부터 비용이 싼것만 골라나가면 최소의 비용을 찾을 수 있을거라고 생각했다. 물론 계속 생각하다보니 누락되는 최소비용들이 존재할거라는 생각이 들긴했다. 그렇다고 재귀함수를 짜서 값을 구하자니 시간제한이 0.5초 밖에 되지 않았다. 아무래도 재귀함수는 아닌거 같아서 고민을 상당히 많이 했다. 고수들의 코드를 슬쩍 보고오니, 최소 비용을 누적시켜서 확인하는 것을 알게 되었다. 즉, i번 집이 R로 칠해진다면 i-1번 집이 칠해지는 값중 가장 싼값을 선택해서 현재의 최종적인 최소비용을 구하는 방식이었다. 따라서 i번째 까지의 최종 비용을 누적 시켜서 n번째 집까지의 최종 비용을 구하는 것이었다. 이게 재밌는게 누적값을 ..