도둑질

https://school.programmers.co.kr/learn/courses/30/lessons/42897?language=python3

프로그래머스

---

1차 시도

dp로 푸는 것을 떠올랐고, 첫 번째 집부터 터는 경우와 두 번째 집부터 터는 경우로 나누어서 각 경우의 마지막 dp 값이 큰 경우가 답이 될 것이라 생각했습니다.

def solution(money):
    N = len(money)
    
    # 첫 번째부터 털 경우 -> 마지막 집 못 텀
    dp = [0] * N
    
    dp[0] = money[0]
    dp[1] = money[0]
    
    for i in range(2, N-1):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
        
    from_first = dp[N-2]
    
    # 두 번째부터 털 경우
    dp = [0] * N
    
    dp[0] = 0
    dp[1] = money[1]
    
    for i in range(2, N):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
        
    from_second = dp[N-1]
    
    return max(from_first, from_second)

결과: 100

정확성, 효율성 모두 통과

 

풀이

현재(i)까지 집을 털었을 때 최대값은 

• i-2 번째까지 집을 털었을 때 최대값(dp[i-2]) +  i 번째 집을 털었을 때
• i-1 번째까지 집을 털었을 때 최대값(dp[i-1])

이 두 경우를 비교해서 더 큰 값이 dp[i]가 됩니다.

 

첫 번째 집을 털 경우 마지막 집은 첫 번째 집과 인접하기 때문에 털 수가 없습니다.

그래서 첫 번째 집부터 털 경우와 두 번째 집부터 털 경우를 구분해야 합니다.

 

첫 번째 집부터 털 경우

첫 번째 집을 털 경우 두 번째 집을 털지 못하기 때문에 dp[0]과 dp[1]는 money[0]이 됩니다.

마지막 집의 바로 전 집(N-2)까지 턴 경우의 최대값이 첫 번째 집부터 털 경우의 최대값(dp[N-2])이 됩니다.

 

두 번째 집부터 털 경우

첫 번째 집을 털지 않고 두 번째 집을 털기 때문에 dp[0]는 0, dp[1]는 money[1]이 됩니다.

마지막 집(N-1)까지 턴 경우의 최대값이 두 번째 집부터 털 경우의 최대값(dp[N-1])이 됩니다.

 

두 경우의 최대값 중 더 큰 값이 정답이 됩니다.