[고득점 kit]_동적계획법_#4. 도둑질

(문제 설명)

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

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

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

제한사항

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

입출력 예moneyreturn

[1, 2, 3, 1]

4

---

(문제 해설)

 

0. 이문제를 보면 현재 검사하는 위치에서 다음 꺼는 못 훔치기 때문에 그 부분을 고려하여 문제를 푼다.

1. 원의 형태이기 때문에 0번째를 털면 끝 인덱스는 털지 못한다

2. 고로 첫번째 인데스를 터는 경우와

2-1. 영번째 인덱스를 터는 경우를 나누어서 풀이한다.

 

---

[ 코드 ]

 

def solution(money):
    answer = 0
    # 한 번에 안되더라 그래서 레벨4 인듯
    dp1 = [0 for _ in range(len(money))]
    dp = []
    # 첫집 선털
    # 2부터 시작하는 이유는 i - 2 되면 -1이 안되게 하려고
    dp1[0] = money[0]
    dp1[1] = money[0]
    for i in range(2, len(money) - 1):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i])
        
    
    # 두집 선털기
    dp2 = [0 for _ in range(len(money))]
    dp2[1] = money[1]
    for i in range(2, len(money)):
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])
        

    # print(dp1, dp2)
    answer = max(dp1[-2], dp2[-1])
    return answer

---

후기

 

설명이 조금 필요한 문제입니다.

설명이 적어서 쉬운 문제는 아닙니다.

다만 코드로 이해하는게 동적 계획법은 대체적으로 그러니

풀이는 간단하게 한 것.