문제 개요
한 도시에 여러 채의 집이 있고, 각 집에는 일정 금액의 현금이 보관되어 있다고 가정해 보겠습니다. 한 명의 강도가 단 하룻밤 사이에 이 돈을 훔치려고 하는데, 이 도시에는 보안 시스템이 설치되어 있어 같은 날 밤에 연속된 두 집이 침입당하면 자동으로 경찰에 신고됩니다. 따라서 강도는 인접한 두 집을 동시에 털 수 없으며, 우리는 이 조건 하에서 강도가 훔칠 수 있는 최대 금액을 구해야 합니다.
금액 정보는 배열로 제공됩니다. 인덱스 i에서 A[i]는 i번째 집에 보관된 금액을 의미합니다. 예를 들어 배열이 A = [2, 7, 10, 3, 1]이라면 정답은 13입니다. 첫 번째 집(2), 세 번째 집(10), 다섯 번째 집(1)을 선택하면 서로 연속되지 않으면서 총합 13으로 가장 큰 값을 얻을 수 있습니다.
풀이 접근 방식
이 문제는 대표적인 동적 계획법(Dynamic Programming) 유형입니다. 각 집을 순회하면서 "현재 집을 털 경우"와 "현재 집을 건너뛰는 경우" 중 더 큰 값을 선택하면 되며, 두 개의 변수만 사용해 O(n) 시간 복잡도로 해결할 수 있습니다.
- prev1 := 0, prev2 := 0으로 초기화합니다.
- i = 0부터 배열 A의 길이까지 반복합니다.
- temp := prev1 (이전 값을 임시 저장)
- prev1 := max(prev2 + A[i], prev1) — 현재 집을 털었을 때와 건너뛰었을 때 중 큰 값 선택
- prev2 := temp
- 반복이 끝나면 prev1을 반환합니다.
여기서 prev1은 "직전 집까지 고려했을 때의 최대 금액", prev2는 "두 집 전까지 고려했을 때의 최대 금액"을 의미합니다. 현재 집을 털려면 바로 앞집은 털면 안 되므로 prev2 + A[i]가 되고, 털지 않는다면 기존의 prev1이 그대로 최대값이 됩니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해할 수 있습니다.
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
prev2 = 0
prev1 = 0
for i in range(0, len(nums)):
temp = prev1
prev1 = max(prev2 + nums[i], prev1)
prev2 = temp
return prev1
ob1 = Solution()
print(ob1.rob([2, 7, 10, 3, 1]))
입력
nums = [2,7,10,3,1]
출력
13