[프로그래머스] 도둑질 (level4, python)

🏝 문제 설명

 

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

 

 

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

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

---

제한사항

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

---

입출력 예

[1, 2, 3, 1]

4

---

🏝 풀이 코드

def solution(money):
    answer = 0
    if len(money) == 1:
        return money.pop()

    size = len(money)
    # 1번 선택하는 경우 -> 1..n-1번 배열에 대한 DP
    dp1 = [0] + money[:-1]
    for i in range(2, size):
        dp1[i] = max(dp1[i-1], dp1[i-2] + dp1[i])
    
    # 2번 선택하는 경우 -> 2...n번 배열에 대한 DP
    dp2 = [0] + money[1:]
    for i in range(2, size):
        dp2[i] = max(dp2[i-1], dp2[i-2] + dp2[i])
        
    answer = max(dp1[-1], dp2[-1])
    return answer

 

원형 DP에 대한 문제이다.

2022.10.14 - [🐍 코딩테스트 대비 : PS] - [프로그래머스] 스티커 모으기(2) (level3, python)

[프로그래머스] 스티커 모으기(2) (level3, python)

 

위 문제와 완전히 동일한 문제이며, 코드마저 동일하다.

Level의 차이가 나는 이유는 도둑질 문제가 효율성 체크를 더 강하게 하기 때문으로 보이는데, 둘 다 원형 DP 풀이로 풀린다.

 

이 문제의 해설에 대해 알고 싶다면, 위 링크의 해설 글에 나와있으니 참고 바란다.