[DP] 프로그래머스 도둑질 (Java 풀이)

프로그래머스

[ 문제 설명 ]

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

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

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

 

[제한 사항]

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

 

[입출력 예]

 

 

[풀이]

이 문제는 프로그래머스 동적계획법(DP) 부분에 있는 레벨4 문제입니다.

 

일단 구해야하는 사항이 돈의 최댓값이기 때문에 dp배열은 dp[i] = 도둑이 i번째 집에 왔을 때의 훔친 돈의 최댓값 이 되어야 함을 느꼈습니다.

 

그리고 나서 이 dp[i]를 어떻게 구해야할지 생각해보니 집은 현재 집을 털거나(그 전전 집의 dp값 + 현재 집이 가진 돈 = dp[i-2]+money[i]), 현재 집을 털지 않거나(i-1 번째 dp 그대로 가져오죠)로 나누어져 dp[i] = Math.max(dp[i-1], dp[i-2]+money[i]) 가 됩니다.

 

하지만 여기서부터 제가 좀 막혔었는데요... 집은 원형으로 되어있는데, 집 하나를 털면 양 옆의 집은 무조건 털 수 없는 구조잖아요..? 

 

근데 조금만 생각해보면, 두 가지 상황으로 나눌 수 있습니다.

 

1. 첫 번째 집을 무조건 털고, 마지막 집을 무조건 털지 않는 경우

2. 첫 번째 집을 무조건 털지 않는 경우

 

그래서 아래와 같은 코드로 구현했습니다.