[파이썬 python] 프로그래머스 - 도둑질

• 도둑질

문제 설명

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

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

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

제한사항

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

입출력 예

moneyreturn

[1, 2, 3, 1]

4

 

---

def solution(money):
    answer = 0
    #첫 번째 집 포함, 마지막 집 비포함
    dp = [0 for _ in range(1000000+1)]
    dp[0] = 0
    dp[1] = money[0]
    #첫 번째 집 비포함, 마지막 집 포함
    dp2 = [0 for _ in range(1000000+1)]
    dp2[0] = 0
    dp2[1] = 0
    
    for i in range(2, len(money)+1):
        if i < len(money):
            dp[i] = max(dp[i-1], dp[i-2]+money[i-1])
            dp2[i] = max(dp2[i-1], dp2[i-2]+money[i-1])
        else:
            dp2[i] = max(dp2[i-1], dp2[i-2]+money[i-1])
    
    answer = max(dp[len(money)-1], dp2[len(money)])
    return answer

 

정확성  테스트
테스트 1 〉	통과 (61.42ms, 25.4MB)
테스트 2 〉	통과 (59.02ms, 25.3MB)
테스트 3 〉	통과 (61.66ms, 25.2MB)
테스트 4 〉	통과 (60.82ms, 25.3MB)
테스트 5 〉	통과 (60.64ms, 25.3MB)
테스트 6 〉	통과 (61.39ms, 25.3MB)
테스트 7 〉	통과 (61.26ms, 25.3MB)
테스트 8 〉	통과 (61.35ms, 25.3MB)
테스트 9 〉	통과 (58.24ms, 25.3MB)
테스트 10 〉	통과 (60.76ms, 25.3MB)
효율성  테스트
테스트 1 〉	통과 (686.73ms, 97.3MB)
테스트 2 〉	통과 (682.80ms, 92.9MB)
테스트 3 〉	통과 (714.94ms, 95.5MB)
테스트 4 〉	통과 (712.33ms, 96.2MB)
테스트 5 〉	통과 (605.06ms, 82.7MB)
테스트 6 〉	통과 (717.47ms, 93.4MB)
테스트 7 〉	통과 (428.98ms, 64.8MB)
테스트 8 〉	통과 (414.76ms, 66MB)
테스트 9 〉	통과 (531.19ms, 72.6MB)
테스트 10 〉	통과 (699.24ms, 94MB)

 

후기

프로그래머스 4단계 문제다. 입력 값이 굉장히 크고, 시간복잡도를 고려해야 하니 DP로 풀어야 하는 문제로 생각했다.

인접할 수가 없으므로, 최소한 한 번씩은 건너 뛰어야 한다.

처음에 계속 틀렸는데, 맨처음 집과 맨 마지막 집이 중복되서 합쳐질 가능성을 무시한 것이 원인이었다.(또한 이것이 이 문제의 핵심이다.)

 

풀이

(1) dp[현재] = max(dp[이전 집의 최댓값] , dp[이전이전 집의 최댓값]+현재 집 값) 으로 dp를 구해주면 된다.

(2) 전체 경우의 수를 단 2가지의 CASE로 분류 할 수있다. CASE1은 시작 집을 포함하고 마지막 집을 포함하지 않는 케이스고, CASE2는 시작 집을 비포함하고 마지막 집을 포함시킨다. (집의 값은 모두 0 이상이다. 어찌됫든 최댓값을 위해선 한 곳을 무조건 포함시켜야 한다. 시작 집과 마지막 집을 모두 포함하지 않을 필요는 없다.)

(3) CASE1(처음 집부터 시작하여 마지막 집의 전 집까지 최댓값)과 CASE2(처음 집은 건너뛰고, 그 다음부터 시작하여 마지막 집까지의 최댓값)를 비교하여 최댓값을 리턴해준다.