동적계획법 - 도둑질

이번 문제는, 동적계획법을 사용하는 문제입니다.

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

코딩테스트 연습 - 도둑질

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

 

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

 

각 집에 있는 돈이 담긴 배열 money가 주어질 때,

 

도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

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

============================================================================

여느 동적계획법 문제가 그렇듯

 

이번 문제도 점화식 관계로 작은 해답으로 부터 최적해를 찾는 문제입니다.

 

문제를 살펴보면, 이웃한 두 집은 동시에 털수 없기 때문에

 

첫번째 집을 포함하는 경우와, 첫번째 집을 제외하는 두가지 Case를 모두 고려해야합니다.

 

문제의 추상화된 이미지

이제, 첫번째 포함/제외로 나눠놓으면서 더이상 원형의 형태가 아니라, 직선 형태로 집이 있다고 할 수 있게됩니다.

 

이제 동적계획법을 생각해 봅시다.

 

N번째 까지 털때 가장 많은 돈

= Max((N-2번째 까지 털때 가장 많은 돈 + N번째 집의돈), N-1번째 까지 털때 가장 많은 돈)

 

의 관계가 성립됩니다.

 

위와같은 방법으로 첫 집이 포함된 경우와 첫 집이 제외된 경우를 모두 계산한 뒤

 

둘중 가장 많은 돈은 번 경우를 선택하면 되겠습니다 :)

 

def solution(money):    
    answer = 0        
    #첫번째를 포함하는경우
    dp = {"init" : money[0],
          "next" : max(money[0],money[1])}    
    money_1 = money[:-1]           
    #첫번째를 제외한 경우
    dp_out = {"init" : money[1],
              "next" : max(money[1], money[2])}    
    money_2 = money[1:]
    
    #순차적으로 첫번째를 포함, 제외하는 경우에 대해서 점화식을 계산
    for i, j in zip(money_1[2:], money_2[2:]):
        answer = max(dp["init"]+i, dp["next"])
        dp["init"] = dp["next"]
        dp['next'] = answer
        
        answer = max(dp_out["init"]+j, dp_out["next"])
        dp_out["init"] = dp_out["next"]
        dp_out['next'] = answer
    return max(dp_out['next'],dp['next'])