문제 개요
당신은 전문 도둑이라고 상상해 봅시다. 한 거리에 늘어선 집들을 털 계획을 세우고 있는데, 각 집에는 일정 금액의 돈이 보관되어 있습니다. 이번 문제의 특징은 모든 집이 원형으로 배치되어 있다는 점입니다. 즉, 첫 번째 집과 마지막 집 역시 서로 이웃입니다.
여기서 주의할 점은 인접한 집들끼리 보안 시스템이 연결되어 있어, 같은 밤에 연속된 두 집을 털면 자동으로 경찰에 신고된다는 사실입니다. 따라서 각 집의 돈의 양을 나타내는 정수 배열이 주어졌을 때, 경찰에 들키지 않고 한밤중에 훔칠 수 있는 최대 금액을 구해야 합니다. 예를 들어 배열이 [1,2,3,1]이라면, 첫 번째 집과 세 번째 집을 털어 답은 4가 됩니다.
접근 방법
이 문제는 동적 계획법(DP)으로 해결할 수 있습니다. 핵심 아이디어는 원형 구조를 두 개의 선형 문제로 나누는 것입니다. 첫 번째 집을 터는 경우(마지막 집 제외)와 털지 않는 경우(첫 번째 집 제외)를 분리하면, 각각은 일반적인 선형 형태의 House Robber 문제가 되므로 두 결과 중 최댓값을 취하면 됩니다.
구체적인 풀이 단계는 다음과 같습니다.
- solve() 함수는 배열 nums와 시작 인덱스 start, 끝 인덱스 end를 인자로 받아 다음과 같이 동작합니다.
- ans := nums[start]
- nums와 같은 크기의 DP 테이블 dp를 생성합니다.
- dp[start] := nums[start]
- i를 start + 1부터 end까지 반복합니다.
- last := dp[i - 1]
- lastToLast := i - 2 < start이면 0, 그렇지 않으면 dp[i - 2]
- dp[i] := nums[i] + lastToLast와 last 중 최댓값
- ans := dp[i]와 ans 중 최댓값
- ans를 반환합니다.
실제 도둑질 로직은 rob() 함수에서 다음과 같이 처리합니다.
- n := nums의 크기
- n이 0이면 0을 반환합니다.
- n이 1이면 nums[0]을 반환합니다.
- solve(nums, 0, n - 2)와 solve(nums, 1, n - 1) 중 최댓값을 반환합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector <int>& nums, int start, int end){
int ans = nums[start];
vector <int> dp(nums.size());
dp[start] = nums[start];
for(int i = start + 1; i <= end; i++){
int last = dp[i - 1];
int lastToLast = i - 2 < start? 0 : dp[i - 2];
dp[i] = max(nums[i] + lastToLast, last);
ans = max(dp[i], ans);
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
if(!n)return 0;
if(n == 1)return nums[0];
return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
};
main(){
vector<int> v = {1,2,3,5};
Solution ob;
cout << ob.rob(v);
}입력
[1,2,3,5]
출력
7
결과 해설
배열 [1,2,3,5]에서 선택 가능한 조합을 살펴보면, 첫 번째 집(1)과 세 번째 집(3)을 털면 4, 두 번째 집(2)과 네 번째 집(5)을 털면 7이 됩니다. 원형 구조상 첫 번째 집과 마지막 집은 동시에 털 수 없으므로, 최댓값은 7입니다.
복잡도 분석
배열을 한 번씩만 순회하므로 시간 복잡도는 O(n), DP 테이블을 저장하기 위한 공간 복잡도는 O(n)입니다.