https://programmers.co.kr/learn/courses/30/lessons/42897
-
flow
동적 계획법을 이용하면 쉽게 풀 수 있는 문제이다. n번째 집까지만 생각했을 때, (n-2 까지의 최댓값 + n번째 집 money) 와 n-1까지의 최댓값 둘을 비교하여 더 큰 값이 n번째의 최댓값이 되고 이를 반복해 나아가면 정답이 나온다. 주의해야할 점이 초기값 설정을 할 때, 임의의 인접한 3개의 집에 대해 반드시 한 집은 포함되어야 하므로, 1번집 포함한 경우, 2번집 포함한 경우, 3번집 즉, 3가지 경우의 시작점을 둔 채로 동적 프로그래밍을 진행한다.
시간 복잡도는 O(3N) = O(N)이 가능하다. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A42897.py
