1. 문제
설명
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
제한사항
- 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
- money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
입출력 예
| money | return |
|---|---|
| [1, 2, 3, 1] | 4 |
2. 풀이
문제를 풀 땐 문제를 작은 부분 문제들로 나눈 다음
차례대로 부분 문제들을 해결하는 식으로 풀면 문제의 접근이 쉬워집니다.
이 문제에서 제일 까다로운 점이 뭘까요?
바로 집들이 원형으로 배치돼있다는 점입니다.
우리는 처음부터 모든 부분을 해결하려하지 말고 작은 부분부터 해결해보기로 했습니다.
고로 일단 모든 집들이 원형이 아니라 일렬로 나열돼있다고 생각해봅시다.
일단 완전 탐색부터 설계합니다.
완전 탐색
#include <vector>
#include <algorithm>
using namespace std;
// 일렬로 나열된 집들을 터는 경우를 모두 탐색하는 함수
int f(int s, int sum, vector<int> *money) {
// 기저 사례 - 모든 집을 다 털었을 때 그동안 모은 sum 리턴
if (s >= money->size()) return sum;
// 현재 집을 털지 않고 다음 집으로 넘어가는 경우 vs 현재 집을 털고 다다음 집으로 넘어가는 경우
return max(f(s + 1, sum, money), f(s + 2, sum + (*money)[s], money));
}
int solution(vector<int> money) {
return f(0, 0, &money);
}일단 별 어려움 없이 완전 탐색 함수를 만들었습니다.
하지만 모든 집에 대해서 턴다, 안 턴다 선택을 하기 때문에
시간 복잡도는 O(2^n)이 돼버리기 때문에 메모이제이션 기법을 적용해봅시다.
메모이제이션
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 메모 배열
int memo[1000001];
// f(s) = s번째 집부터 털었을 때 얻을 수 있는 최댓값
int f(int s, vector<int> *money) {
// 기저 사례 - 모든 집을 털었을 때 0을 리턴
if (s >= money->size()) return 0;
int &ret = memo[s];
if (ret != 0) return ret;
// 현재 집을 털지 않고 다음 집부터 털었을 때 얻을 수 있는 최댓값
// vs
// 현재 집을 털고 다다음 집부터 털었을 때 얻을 수 있는 최댓값
return ret = max(f(s + 1, money), (*money)[s] + f(s + 2, money));
}
int solution(vector<int> money) {
return f(0, &money);
}이번에도 별 어려움 없이 메모이제이션을 적용할 수 있었습니다.
하지만 지금까지 작성한 함수는 일렬로 나열된 집을 터는 데에만 포커싱된 코드라는 겁니다.
어떻게 하면 원형으로 나열된 집을 터는 문제로 전환할 수 있을까요?
f(s) = s번째 집부터 털었을 때 얻을 수 있는 최댓값
f(s) = max(f(s + 1), money[s] + f(s + 2));
우리는 메모이제이션을 적용하면서 위의 점화식을 얻을 수 있었습니다.
이제 생각을 조금만 더 하면 위의 점화식을 이용해서
'원형으로 나열된 집을 털 때도 해결할 수 있겠다'라고 생각이 들 수 있습니다.
왜냐하면 원형으로 나열된 집을 터는 경우는
0번째 집부터 n - 1집까지 터는 경우와
1번째 집부터 n번째 집까지 터는 경우로 나눠서 생각할 수 있기 때문입니다.
그러면 위의 함수를 우리가 원하는 형태로 조금만 변형시켜봅시다.
f(s, e) = s번째 집부터 e까지 털었을 때 얻을 수 있는 최댓값
인자로 e변수를 추가했습니다.
이제 원형으로 나열된 집을 터는 최댓값을 이와 같이 도출됩니다.
int answer = max(f(0, n - 1), f(1, n));
0번째 집부터 n - 1집까지 터는 경우와 1번째 집부터 n번째 집까지 터는 경우중에서
최댓값이 우리가 원하는 정답이 됩니다.
Top-down 전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int memo1[1000001]; // 0번째 집부터 털 때 쓰는 메모이제이션 배열
int memo2[1000001]; // 1번째 집부터 털 때 쓰는 메모이제이션 배열
int f(int s, int e, int *memo, vector<int> *money) {
// 기저 사례 - e번째 집까지 털었을 때 0을 리턴
if (s >= e) return 0;
int &ret = memo[s];
if (ret != 0) return ret;
return ret = max(f(s + 1, e, memo, money), (*money)[s] + f(s + 2, e, memo, money));
}
int solution(vector<int> money) {
// 0 ~ n-1까지 터는 경우 vs 1 ~ n까지 터는 경우
return max(f(0, money.size() - 1, memo1, &money), f(1, money.size(), memo2, &money));
}c++로 작성시 위 탑다운 코드는 효율성까지 통과가 가능하지만 java로 작성하면 통과하지 못합니다...
아무래도 재귀 함수다 보니 함수 호출 비용과 기저 사례인지 비교하는 로직이 계속 연산되기 때문에 그런 듯합니다.
하지만 괜찮습니다.
저번 포스팅 등굣길에서도 알아봤듯이 top-down코드를 작성했다면 bottom-up코드도 쉽게 작성할 수 있습니다.
Bottom-up 전체 코드
#include <vector>
#include <algorithm>
using namespace std;
int dp1[1000001]; // 0번째 집부터 털 때 쓰는 dp 배열
int dp2[1000001]; // 1번째 집부터 털 때 쓰는 dp 배열
int solution(vector<int> money) {
int n = money.size();
dp1[1] = money[0];
for (int i = 2; i <= n - 1; i++) {
dp1[i] = max(dp1[i - 1], money[i - 1] + dp1[i - 2]);
}
dp2[2] = money[1];
for (int i = 3; i <= n; i++) {
dp2[i] = max(dp2[i - 1], money[i - 1] + dp2[i - 2]);
}
return max(dp1[n - 1], dp2[n]);
}bottom-up은 초기값 설정과 반복문 설정이 조금 불편하지만
문제에 따라 top-down보다 더 짜기 쉬워지는 경우도 종종 있기 때문에
bottom-up, top-down 둘 다 연습하시는 걸 추천드립니다.
