[Programmers / Python / 동적계획법] - 도둑질

출처 https://programmers.co.kr/learn/courses/30/lessons/42897

Q.

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

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

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

입출력 예
money return
[1, 2, 3, 1] 4

나의 풀이

1

처음부터 max인 집부터 시작해 해당 집의 양 옆을 제외시키고 다시 남은 집 중에서 max를 뽑는 것을 반복하는 방식으로 코드를 작성했다.

def solution(money):
    answer = 0
    while (True):
        if sum(money) == -1*len(money):
            break

        now = money.index(max(money))
        answer += money[now]
        money[now], money[(now+1) % len(money)], money[(now-1) % len(money)] = -1, -1, -1
    
    return answer

하지만 질문하기의 테스트 케이스를 통해 위의 코드를 확인해봤는데 [91,90,5,7,5,7] 를 통해 나의 코드가 틀렸다는 것을 깨달았다.

print("테스트 케이스 결과 비교 (내 코드 / 정답)")
print(solution([1,2,3,1]), 4)
print(solution([1,1,4,1,4]), 8)
print(solution([1000,0,0,1000,0,0,1000,0,0,1000]), 3000)
print(solution([1000,1,0,1,2,1000,0]), 2001)
print(solution([1000,0,0,0,0,1000,0,0,0,0,0,1000]), 2000)
print(solution([1,2,3,4,5,6,7,8,9,10]), 30)
print(solution([0,0,0,0,100,0,0,100,0,0,1,1]), 201)
print(solution([11,0,2,5,100,100,85,1]), 198)
print(solution([1,2,3]), 3)
print(solution([90,0,0,95,1,1]), 185)
print(solution([91,90,5,7,5,7]), 104)

2 (통과)

dp1[n], dp2[n] : n번째 집을 지나는 순간의 최댓값 (n은 훔칠 수도 있고 안훔칠 수도 있다.)
(dp1) 0번째 집 훔치는 경우
(dp2) 0번째 집 훔치지 않는 경우
마지막에 max(dp1[-1], dp2[-1])

def solution(money):
    length = len(money)

    # 0 번째 집 훔치는 경우
    dp1 = [0] * (length - 1)
    dp1[0] = money[0]
    dp1[1] = dp1[0]
    for i in range (2, length-1): # 마지막 집은 갈 필요 없다.
        dp1[i] = max(dp1[i-1], dp1[i-2]+money[i])

    # 0 번째 집 훔치지 않는 경우
    dp2 = [0] * length
    dp2[0] = 0
    dp2[1] = money[1]
    for j in range (2, length): # 마지막 집까지 확인해보긴 해야함
        dp2[j] = max(dp2[j-1], dp2[j-2]+money[j])
        
    return max(dp1[-1], dp2[-1])