Programmers / 도둑질 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 도둑질 (4단계) - 동적 계획법

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

문제 설명

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

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

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

제한사항

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

입출력 예moneyreturn

[1, 2, 3, 1]

4

---

나의 풀이

def solution(sticker):
    answer = 0
    if len(sticker) <= 3:
        return max(sticker)
    dp1 = [0]
    dp2 = [0]
    dp1.extend([sticker[i] for i in range(len(sticker)-1)])
    dp2.extend([sticker[i] for i in range(1,len(sticker))])
    
    i = 2
    while i < len(sticker):
        dp1[i] = max(dp1[i-1],dp1[i-2] + dp1[i])
        dp2[i] = max(dp2[i-1],dp2[i-2] + dp2[i])
        i+= 1


    return max(max(dp1),max(dp2))

---

※ 알아야 할 것

- 프로그래머스 3단계 스티거모우기(2)와 똑같은 문제임