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

 

 

나의 풀이

def solution(money):
   
    # 방법1. 맨 뒷 집을 제외한 경우 
    dp1 = [0]*len(money)
    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1]) # 0,1번 집 중 더 돈이 많은 집 하나만 털 수 있음
 
    for i in range(2,len(money)) :
        if i != len(money) - 1 :
            dp1[i] = max(dp1[i-2]+money[i], dp1[i-1])
        else :
            dp1[i] = max(dp1[i-2]+0, dp1[i-1]) # 마지막집이 없다고 가정했으므로 dp[i] 는 i-2, i-1 중 더 큰 값이 된다.
        
    
    # 방법2. 맨 앞 집을 제외한 경우
    dp2 = [0]*len(money)
    dp2[0] = 0 # 맨 앞집을 0으로 두어 제외함
    dp2[1] = money[1]

    for i in range(2, len(money)) :
        dp2[i] = max(dp2[i-2]+money[i], dp2[i-1])
        
    return max(dp1[len(money)-1],dp2[len(money)-1])

• 마을의 집은 원형으로 이루어져있기 때문에, 첫번째집을 제외하고 문제를 푼 결과 / 마지막집을 제외하고 문제를 푼 결과 둘 중 더 큰 값을 정답으로 채택하는 것이 이 문제의 핵심이다.
• dp[i] 는 0~i 까지 집들을 선택하면서 훔친 돈의 최댓값을 뜻한다.
• 따라서  dp[i] = max(dp[i-2]+money[i], dp[i-1]) 라는 점화식을 도출해낼 수 있다. 
• i-2까지의 최댓값 + i번째집을 털었을 때 vs i-1까지의 최댓값 중 더 큰 값이 dp[i] 이 되기 때문이다.

 

 

예) money = [10, 2, 2, 100, 2] 가 주어졌다고 가정해보자.

• 10과 2는 동시에 선택될 수 없기 때문에 10,2,2,100,0 / 0,2,2,100,2 라는 서로 다른 마을이 있다고 생각하고 문제를 풀어야 한다.
• 마지막집을 배제한 경우 : 10,2,2,100,0  
  • dp[0] = 10 / 선택된 집 : 0
  • dp[1] = max(10,2) = 10 / 선택된 집 : 0
  • dp[2] = max(10+2, 10) = 12 / 선택된 집 : 0, 2
  • dp[3] = max(10+100, 12) = 110 / 선택된 집 : 0, 3
  • dp[4] = max(12,110) = 110 / 최종선택된 집 : 0, 3
• 첫번째집을 배제한 경우 : 0,2,2,100,2
  • dp[0] = 0 / 선택된 집 : 0
  • dp[1] = max(0,2) = 2 / 선택된 집 : 1
  • dp[2] = max(0+2, 2) = 2 / 선택된 집 : 0,2 or 1
  • dp[3] = max(2+100, 2) = 102 / 선택된 집 : 1,3
  • dp[4] = max(2+2, 102) = 102 / 최종선택된 집 : 1,3
• 마지막집을 배제한 경우 : 110 , 첫번째집을 배제한 경우 : 102 -> 더 큰 값 110