프로그래머스 등굣길 (파이썬)

Level 4, DP

 

문제: https://programmers.co.kr/learn/courses/30/lessons/42897#

코딩테스트 연습 - 도둑질

문제 설명

접한 두 집을 털면 경보

처음과 마지막이 연결된 원형

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값 출력

 

제한사항

• 3 <= 집 개수 <= 1,000,000
• 0 <= money <= 1,000 정수

입출력 예

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

첫번째 제출 코드(오답)

이것이 코딩테스트다의 개미전사와 비슷하게 dp를 다음과 같이 구성했습니다.

dp[i] = max(dp[i-2]+money[i-1], dp[i-1]) 

처음과 끝이 같을 수도 있는 예외를 처리 못해 틀렸습니다.

 

두번째 제출 코드(정답)

def solution(money):
    answer = 0
    n = len(money)
    dp = [0] * (n+1)
    dp[1] = money[0]
    dp[2] = max(money[0], money[1])
    if n == 3:
        return max(money)
    
    #첫번째 무조건 털기 = 맨뒤를 고려 안함
    for i in range(3, n):
        dp[i] = max(dp[i-2]+money[i-1], dp[i-1])
    MAX1 = dp[n-1]
    
    #마지막 무조건 털기 = 처음을 고려 X
    dp = [0] * (n+1)
    dp[2] = money[1]
    dp[3] = max(money[1], money[2])
    for i in range(4, n+1):
        dp[i] = max(dp[i-2]+money[i-1], dp[i-1])
    MAX2 = dp[n]

    return max(MAX1, MAX2)

 

도저히 방법이 생각나지 않아 검색을 하여 힌트를 얻었습니다.

풀이는 생각보다 복잡하지 않았습니다.

두 가지로 나눠서 생각하면 됩니다.

먼저 첫번째를 무조건 선택하는 경우 입니다. 이 경우는 맨 뒤를 뽑지 않는 경우와 같은 의미이므로 n-1까지만 dp를 구했습니다.

다음은 첫번째를 무조건 선택하지 않는 경우입니다. 이 경우는 마지막까지 확인한다는 의미로 dp을 n까지 구하는 대신 2부터 시작했습니다. 

그 후 두 dp의 최대값을 비교하는 식으로 답을 구했습니다.

 

다음은 제가 이 문제를 해결하기 위해 사용한 반례입니다.

 

[1, 2, 3], 3

[1, 2, 3, 99, 1], 101

[1000, 1000, 1], 1000

[11, 0, 2, 5, 100, 100, 85, 1], 198

[1000, 0, 0, 1000, 0, 0, 1000, 0, 0, 1000], 3000

[0, 0, 0, 0, 100, 0, 0, 100, 0, 0, 1, 1], 201

[0, 0, 2, 1, 0, 0, 1], 3

[10, 2, 2, 100, 2], 110