[프로그래머스] 도둑질 (파이썬)

문제 링크

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

코딩테스트 연습 - 도둑질

 

문제풀이

원을 따라 위치한 집들을 털 때, 최대로 훔칠 수 있는 값을 리턴하는 문제이다.

이 문제에서는 기준점을 정해주는 것이 풀이의 첫단추를 꿰는 것이다.

 

나는 1번 째 집을 기준점으로 정했고,

1번째 집을 터는 경우와 털지 않는 경우 두 가지로 나누어서, 두 케이스 중 최댓값을 리턴하는 식으로 진행했다.

그리고 1번째 집부터 n 번째 집까지 순서대로 턴다고 가정하고, 각 단계에서 최대로 많이 털 수 있는 값을 가져오는 식으로 dp 를 짰다.

 

1번 째 집을 터는 경우엔, 마지막 집과 2번째 집을 털지 못하므로, dp[2] 와 dp[n] 은 0 이다.

dp[3] 은 자연스럽게 dp[1] + v[3] 이 되며, dp[1], dp[2], dp[3] 의 값을 구했으므로 점화식을 이용하여 풀면된다.

점화식은

dp[k] = v[k] + max(dp[k-2], dp[k-3]) 으로 구할 수 있다.

 

1번째 집을 털지 않는 경우엔, 

dp[1] = 0 이고, dp[2] 는 v[2], dp[3] 은 v[3] 으로 정할 수 있다.

이 경우에도 첫번째 경우와 마찬가지로 점화식을 적용해서 풀면된다.

 

시간복잡도

집의 최대 개수는 1,000,000 이다.

dp[k] 를 채우기 위해서 dp[k-2], dp[k-3] 을 비교하면 되므로

시간 복잡도는 2 * n 즉, O(N) 이다.

 

소스코드

def solution(money):
    case1 = [0] * len(money);
    case2 = [0] * len(money);
    
    # 0번째 집을 털경우 case1
    case1[0] = money[0];
    case1[1] = 0;
    case1[2] = case1[0] + money[2];
    
    for i in range(3, len(money)):
        case1[i] = money[i] + max(case1[i - 2], case1[i - 3]);
    case1[len(money) - 1] = 0;
    # 0번째 집을 털지 않을 경우 case2
    case2[0] = 0;
    case2[1] = money[1];
    case2[2] = money[2];
    
    for j in range(3, len(money)):
        case2[j] = money[j] + max(case2[j - 2], case2[j - 3]);
    
    answer = max(max(case1), max(case2));
    return answer