220522 - 도둑질

◾ 도둑질 : 프로그래머스 LEVEL 4

• 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

---

◾ 풀이

1. 해설

• 동적 계획법을 활용하여 해결할 수 있다.
• 집이 원형으로 이루어져 있기 때문에 2가지 경우가 있다.
  • 첫 번째 집을 포함하는 경우(마지막 집 선택 불가)
  • 마지막 집을 포함하는 경우(첫 번째 집 선택 불가)
• 2가지 경우를 모두 탐색하여 최대값을 찾는다.
  • 인접한 집은 선택할 수 없으므로 이를 주의한다.

---

2. 프로그램

1. 2가지 경우 모두 탐색
   (1) 첫 번째 집을 포함하는 경우
   (2) 마지막 집을 포함하는 경우
2. 2번째 집까지의 dp 초기화((1) : 첫 번째, 두 번째 집 | (2) : 두 번째, 세 번쨰 집))
3. 이후의 집 선택에 따른 최대값을 저장하며 진행(answer과 비교)
   • 해당 집을 선택하는 경우와 선택하지 않는 경우

# 코드
def solution(money):
    answer = 0
    size = len(money)

    for i in range(2):
        dp = [[0 for _ in range(size-1)] for __ in range(2)]
        dp[1][0] = money[i]
        dp[1][1] = money[i+1]
        dp[0][1] = money[i]
        answer = max(dp[1][0], dp[1][1], answer)

        for idx in range(2, size -1):
            dp[0][idx] = max(dp[1][idx-1], dp[0][idx-1])
            dp[1][idx] = max(dp[1][idx-2], dp[0][idx-1]) + money[idx+i]
            answer = max(dp[0][idx], dp[1][idx], answer)

    return answer