[Programmers] 도둑질 바로가기
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
money | return |
---|---|
[1, 2, 3, 1] | 4 |
Dynamic Programming
)을 적용하면 문제를 해결할 수 있다.dp1 = [0] * N
dp1[0], dp1[1], dp1[2] = money[0], money[1], money[0] + money[2]
for i in range(3,N-1):
dp1[i] = money[i] + max(dp1[i-2],dp1[i-3])
dp1
배열의 첫 번째(0
), 두 번째(1
), 세 번째(2
) 원소의 값을 초기화 한다.3
) 집부터 N-1
번째 집까지 차례로 두 칸 떨어진 집(i-2
) 혹은 세 칸 떨어진 집(i-3
) 중 털었을 경우 더 많은 이득을 주는 집을 선택하여 값을 누적으로 더한다.dp2 = [0] * N
dp2[1], dp2[2] = money[1], money[2]
for i in range(3,N):
dp2[i] = money[i] + max(dp2[i-2],dp2[i-3])
dp2
배열의 두 번째(1
), 세 번째(2
) 원소의 값을 초기화 한다.3
) 집부터 마지막(N
) 집까지 차례로 두 칸 떨어진 집(i-2
) 혹은 세 칸 떨어진 집(i-3
) 중 털었을 경우 더 많은 이득을 주는 집을 선택하여 값을 누적으로 더한다.def solution(money):
answer = 0
N = len(money)
if N < 4: return max(money)
# [1] 첫 번째 집 포함 and 마지막 집 미포함
dp1 = [0] * N
dp1[0], dp1[1], dp1[2] = money[0], money[1], money[0] + money[2]
for i in range(3,N-1):
dp1[i] = money[i] + max(dp1[i-2],dp1[i-3])
# [2] 첫 번째 집 미포함 and 마지막 집 포함
dp2 = [0] * N
dp2[1], dp2[2] = money[1], money[2]
for i in range(3,N):
dp2[i] = money[i] + max(dp2[i-2],dp2[i-3])
return max(max(dp1),max(dp2))