[Programmers] level4 - 도둑질 (Python) : 동적계획법

▶도둑질 - 동적계획법 (level 4)

▶문제

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

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

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

 

▶제한사항

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

 

▶출력

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

 

▶풀이

dp를 이용해서 푸는 문제이지만 조건이 두 개다.

그냥 일자로 나열된 집을 도둑질한다면 아무 조건 없이 for문 하나로 하면 될 것이다.

하지만 원형이기 때문에 1번 집을 선택하면 마지막 집을 선택할 수 없고,

선택하지 않았다면 마지막 집을 선택할 수 있을 것이다.

따라서 그에 맞춰서 두 가지로 문제를 풀어 그중 max값을 출력해주거나 return 해주면 될 것이다.

 

def solution(money):
    answer = 0
    dp = [0 for _ in range(len(money))]
    
    #첫번째집 훔친다
    dp[0] = money[0]
    dp[1] = money[0]
    
    for i in range(2, len(money)-1):
        dp[i] = max(dp[i-1], dp[i-2] + money[i])
    answer = max(dp)
    
    #첫번째집 x
    dp[0] = 0
    dp[1] = money[1]
    
    for i in range(2, len(money)):
        dp[i] = max(dp[i-1], dp[i-2] + money[i])
    if answer < max(dp):
        answer = max(dp)
    return answer

 

정확성 테스트 및 효율성 테스트 결과이다.

dp로 풀었다면 효율성까지 당연히 만점이 나올것이다.

 

정확성 테스트

테스트 1 〉	통과 (0.22ms, 10.2MB)
테스트 2 〉	통과 (0.60ms, 10.2MB)
테스트 3 〉	통과 (0.33ms, 10.1MB)
테스트 4 〉	통과 (0.04ms, 10.3MB)
테스트 5 〉	통과 (0.16ms, 10.3MB)
테스트 6 〉	통과 (0.40ms, 10.2MB)
테스트 7 〉	통과 (0.25ms, 10.3MB)
테스트 8 〉	통과 (0.18ms, 10.1MB)
테스트 9 〉	통과 (0.61ms, 10.2MB)
테스트 10 〉	통과 (0.14ms, 10.3MB)

효율성 테스트

테스트 1 〉	통과 (609.16ms, 68.8MB)
테스트 2 〉	통과 (517.07ms, 65.4MB)
테스트 3 〉	통과 (602.22ms, 67.5MB)
테스트 4 〉	통과 (600.21ms, 68.1MB)
테스트 5 〉	통과 (539.39ms, 56.8MB)
테스트 6 〉	통과 (572.14ms, 65.7MB)
테스트 7 〉	통과 (309.76ms, 42.1MB)
테스트 8 〉	통과 (353.60ms, 43.2MB)
테스트 9 〉	통과 (371.93ms, 48.6MB)
테스트 10 〉	통과 (594.69ms, 66.3MB)

채점 결과

정확성: 50.0

효율성: 50.0

합계: 100.0 / 100.0