프로그래머스 level4 [도둑질]

출처 : https://programmers.co.kr/learn/courses/30/lessons/42897

 

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

money                                                                                                                                   return

[1, 2, 3, 1]

4

 

dp문제

인접한 집은 털 수 없으므로, 첫번째 집을 털게 되면 마지막 집은 털지 못한다.(원형으로 구성되어 있어서)

그래서 우선, 첫번째 집을 털 것이냐 안 털 것이냐로 나뉜다.

이 두가지 경우 모두 점화식은 같다.

전전집 + 해당 집을 터는 것이 이득인지, 아니면 전집을 터는 것이 이득인지 보면 된다.

따라서 수식은 dp[x] = max(dp[x-2]+money[x], dp[x-1]) 와 같다.

이렇게 계산한 뒤 첫번째 집을 털었을 때와 안 털었을 때 이 두 가지 경우 중 큰 값을 선택해주면 된다.