[TIL] 250627 프로그래머스 - 도둑질

문제 설명

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

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

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

제한사항

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

입출력 예

money	return
[1, 2, 3, 1]	4

---

나의 답

def making_dp(money):
    n = len(money)
    money.insert(0,0) # 더미 변수 추가
    dp = [0] * len(money)
    
    if n >= 1:
        dp[1] = money[1]
    if n>= 2:
        dp[2] = money[2]
    if n>= 3:
        dp[3] = dp[1] + money[3]
    for i in range(4, len(money)):
        dp[i] = max(dp[i-2]+money[i], dp[i-3] + money[i])
    # print(dp)
    return dp
    
def solution(money):
    # 1. 첫번째 집 무조건 선택하는 경우
    money1 = money.copy()[2:-1]
    n1 = len(money1)
    dp1 = making_dp(money1)
    compare1 = max(dp1[-1], dp1[-2]) + money[0]
    
    # 2. 첫번재 집 선택 하지 않는 경우
    money2 = money.copy()[1:]
    dp2 = making_dp(money2)
    compare2 = max(dp2[-1], dp2[-2])
    
    answer = max(compare1,compare2)
    return answer

• 풀이과정을 떠올린 과정은 아래와 같습니다.