je_record

문제 원형으로 이루어진 마을의 집에는 돈이 있다. 인접한 두 집을 털면 경보가 울린다. 이 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구한다. 접근 규칙을 한번에 찾기 힘든 문제라 배열의 길이를 늘리면서 생각해보았다. [1, 2] 집이 2개라면 당연히 돈이 더 많은 2를 선택 [1, 2, 3] 집이 3개라면 당연히 3 선택 [1, 2, 3, 4] 2와 4 선택 [1, 10, 20, 4, 40] 20과 40 선택 그렇다면 점화식은 어떻게 세워야 할까??? [1, 10, 20, 4, 40]을 자세히 살펴보면 최대한 큰 수를 고를 수 있는 모든 경우를 알아보기 위해, 각 위치에서 최대한 큰 값을 고를 수 있는 경우를 알아야 한다. 앞에서부터 각 위치에서 가장 큰 경우를 따져보자. 1: 가장 큰 경우는 당연히 자..