🛠 문제
👩🏻💻 해결 방법
현재 집을 도둑질 하거나 하지 않을 경우로 나누어,
dp[i] = max(dp[i-1], dp[i-2] + money[i])와 같은 점화식을 세울 수 있었다
처음에는 원형을 일자로 펼쳐서 생각해서 문제를 풀었기 때문에 실패를 하였다...
그러나 일자로 생각해서 풀면 처음 집과 마지막 집이 연결되어 있는 경우를 생각하지 못하기 때문에, 처음 집을 도둑질 하는 경우와 도둑질 하지 않는 경우로 나누어서 점화식을 구해주어야 했다
소스 코드
def solution(money):
n = len(money)
dp1 = [0] * n
dp1[0] = money[0]
dp1[1] = max(money[0], money[1])
for i in range(2, n-1):
dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
dp2 = [0] * n
dp2[0] = 0
dp2[1] = money[1]
for i in range(2, n):
dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])
return max(max(dp1), max(dp2))