문제 설명
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
제한사항
이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
문제 풀이
먼저 어쩔 수 없이 DP라는 카테고리에 들어있기 때문에 가장 작은 단위의 문제를 찾아서 거기서 규칙을 찾는 것이 중요하다.
문제 설명에서 가장 중요한 규칙은 "서로 인접한 두 집이 털면 경보가 울린다" 는 부분일 것이다.
이 말은 즉슨 집 3개가 있다면, 중간의 집을 털었을 때의 이익이 클것인지 , 양 사이드의 집을 털때 더 이득일 것인지를 구분해 나가는 구조이다.
집 i 번째 까지의 총 최대 값을 dp에 저장한다고 가정한다면 dp[i] = max(현재 집의 이득, 현재집 -1의 이득 + 현재집 +1의 이득 ) 미래의 값을 가져올 수 없으니까 dp[i] = max(현재 집-1의 이득, 현재집 의 이득 + 현재집 -2의 이득 ) = dp[i] = max(dp[i-1], money[i]+ dp[i-2])
def solution(money):
answer = 0
dp = [0] * len(money)
for i in range (len(money)):
dp[i] = max(dp[i-1],money[i] + dp[i-2])
return max(dp)그런데 문제가 발생했다. 로직은 맞는 것 같은데 에러가 나서 그려봤는데 원형 구조이기 때문에 마지막~처음 집에 중복이 생기게 된다. 집이 n 개일 때,dp[0] = max(dp[n],dp[n-1]+money[0]) 에서 중복이 발생하게 된다. 그래서 중복을 없애기 위해 0번 째 집을 터는 경우와 안턴 경우로 나눠 비교를 하면 된다.
def solution(money):
dp = [0] * len(money) # 0번째 집을 털지 않은 경우
dp[1] = money[1]
for i in range (2,len(money)):
dp[i] = max(dp[i-1],money[i] + dp[i-2])
dp1= [0] * len(money) # 0번째 집을 털 경우
dp1[0] = money[0]
dp1[1] = max(dp1[0],money[1])
for i in range (2,len(money)-1):
dp1[i] = max(dp1[i-1],money[i] + dp1[i-2])
return max(max(dp),max(dp1))