[코딩테스트] 프로그래머스 - 도둑질 (Lv.4) in Python

도둑이 어느 마을을 털려 하고 있습니다. 이 마을의 집들은 동그랗게 배치되어 있습니다.

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

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

- 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.

- money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

 

예시: money = [1, 2, 3, 1], 정답 = 4

 

 

programmers.co.kr/learn/courses/30/lessons/42897

 

풀이!

- 역시나 동적계획법이므로, 각 위치에 도달하기까지의 최댓값을 배열에 넣어주면 된다.

ex. money = [1, 2, 3, 1] 일 때,

    세 번째 집까지 도둑이 갔을 때 여태 털었던 돈의 최댓값은

    1 + 3 = 4.

 

- 따라서, 여태 털었던 돈 최대 value를 저장해주는 배열

dp = [0] * len(money)를 초기화 하고

dp[i] =  max(dp[i-1], dp[i-2]) + money[i] 로 계산해준다.

 

- 어려운 점은, 집들이 원형으로 배열돼 있기 때문에,

첫 번째 집을 선택했다면 마지막 집을 선택하지 말아야한다는 점이다.

- 이를 추적하는 점은 쉬운 일이 아니다. 매 번 자기 위치에서 2, 혹은 3씩 떨어진 값들만 바라보기 때문에,

그 전 값이 첫 번째 값을 포함하는 지 추적하는 건 어렵다.

- 따라서, 첫 번째 집을 털었을 때 / 안 털었을 때 경우를 따로 생각해주자.

전자의 경우, 마지막 집의 값에서 첫번째 집의 값을 뺀다.

 

파이썬 코드

def solution(money):
    # 첫 번째 집 터는 경우
    dp1 = [0]*len(money)
    i = 0
    while i < len(money):
        dp1[i] = max(dp1[i-2], dp1[i-3]) +money[i]
        i += 1
    dp1[-1] -= money[0]

    # 첫 번째 집 안 터는 경우
    dp2 = [0] * len(money)    
    j = 1
    while j < len(money):
        dp2[j] = max(dp2[j-2], dp2[j-3]) +money[j]
        j += 1
    
    answer = max(dp1[-3],dp1[-2],dp1[-1],dp2[-2], dp2[-1])
    
    return answer

- 정확성 테스트 1번 & 10번이 계속 틀려 애를 먹었었는데, dp1에서 맨 끝 두 원소만 살펴봤기 때문이었다.

 

- 반례:  만약

money = [90, 0, 0, 95, 1, 1] 라면,

dp1 = [90, 0, 90, 185, 91, 96],

dp2 = [0,0,0, 95, 1, 96]가 되어,

dp1[-3:]와 dp2[-2:]을 살펴봐야됨을 알 수 있다.

money의 길이가 홀수인 경우, 마지막 원소엔 첫 번째 집 값이 포함되지 않기 때문에, 

첫 번째 집 값을 포함한 최댓값은 뒤에서 세 번째 원소가 될 수도 있기 때문!

 

- 레벨 4 문제는 거의 처음인 것 같은데, 재미있었다!