(Python/LV4) 도둑질

문제 설명:

 

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

도둑질

배치되어 있습니다.

 

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

 

 

제한사항

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

def solution(money):
    firsthome_dp = [0] * len(money)
    secondhome_dp = [0] * len(money)

    # 첫 집 털었을경우
    firsthome_dp[0] = money[0]
    firsthome_dp[1] = money[0]
    for i in range(2,len(money)-1):
        firsthome_dp[i] = max(firsthome_dp[i-2] + money[i],firsthome_dp[i-1])

    # 첫 집 안 털었을 경우
    secondhome_dp[1] = money[1]
    for i in range(1,len(money)):
        secondhome_dp[i] = max(secondhome_dp[i-2]+money[i],secondhome_dp[i-1])

    return max(firsthome_dp[-2], secondhome_dp[-1])
print(solution([1, 2, 3, 1]))

 

 

첫 번째 집을 털었을경우와, 첫 번쩨 집을 털지 못했을 경우를 구분해서 둘 중 큰값을 리턴하면 된다.

 

첫 집을 털었을 경우, 맨 마지막 집은 절대 털 수 없다. 왜냐하면 둘이 붙어있기 때문이다. (len(money)-1)

첫집을 털지 않았을 경우에는 맨 마지막 집을 털수 있다. (len(money))

 

firsthome[-2] 를 하는 경우는 -1 은 맨 마지막집을 털 경우인데, 첫 집을 털면 절대로 털 수 없다.