❔ 문제 요약
모든 물건을 A도둑 또는 B도둑 중 한 명이 훔쳐야 한다.
각 물건을 훔칠 때 A가 훔치면 A의 흔적이 쌓이고, B가 훔치면 B의 흔적이 쌓인다.
단, 두 도둑 모두 경찰에 붙잡히면 안 된다.
- A도둑은 흔적이 n 이상이면 잡힘
- B도둑은 흔적이 m 이상이면 잡힘
따라서 항상 다음 조건을 만족해야 한다.
A 흔적 < n
B 흔적 < m이 조건을 만족하면서 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 최솟값을 구하는 문제다.
⛔️ 틀린 코드
처음에는 모든 경우를 재귀로 탐색
#include <string>
#include <vector>
#include <climits>
using namespace std;
// A도둑이 남긴 흔적의 누적 개수의 최솟값을 return
int Func(vector<vector<int>> &info, int n, int m, int idx, int cur_n, int cur_m){
// base
if(idx==info.size()) return cur_n;
// recursive
// A 도둑의 훔칠 경우
int tmp_a=INT_MAX;
if(cur_n+info[idx][0] < n) tmp_a=Func(info, n, m, idx+1, cur_n+info[idx][0],cur_m);
// B 도둑이 훔칠 경우
int tmp_b=INT_MAX;
if(cur_m+info[idx][1] < m) tmp_b=Func(info, n, m, idx+1, cur_n, cur_m+info[idx][1]);
return min(tmp_a,tmp_b);
}
int solution(vector<vector<int>> info, int n, int m) {
int ans = Func(info,n,m,0,0,0);
return ans==INT_MAX?-1:ans;
}-> 시간 초과 발생
만약 info 길이가 5개일때 다음과 같이 선택한 경우를 탐색한다고 하면
AAAAB
AAAAA
이렇게 마지막 선택만 다른데도 앞쪽의 똑같은 값을 반복 계산 하게 된다.
따라서 물건 개수가 최대 40개일 때 최악의 경우 시간복잡도는 2^40
🔑 해결 전략: 메모이제이션
이 문제는 같은 상태가 여러 번 반복해서 등장한다.
재귀 함수의 상태는 다음 3가지로 정의할 수 있다.
idx : 현재 몇 번째 물건을 훔칠 차례인지
cur_n : 현재까지 쌓인 A도둑의 흔적
cur_m : 현재까지 쌓인 B도둑의 흔적
즉, 같은 상태인
(idx, cur_n, cur_m)가 다시 등장한다면, 그 이후의 결과는 항상 같다.
따라서 이미 계산한 상태는 다시 계산하지 않고 저장된 값을 사용하면 된다.
💙 Step 1: memo 정의
memo[idx][cur_n][cur_m]의 의미는 다음과 같다.
idx번째 물건부터 훔칠 차례이고,
현재 A 흔적이 cur_n,
현재 B 흔적이 cur_m일 때,
최종적으로 가능한 A 흔적의 최솟값
💙 Step 2: 선택지 탐색
각 물건마다 선택지는 2개다.
1. A도둑이 훔치는 경우
cur_n + info[idx][0] < n이면 A도둑이 잡히지 않으므로 선택 가능하다.
Func(info, n, m, idx + 1, cur_n + info[idx][0], cur_m)
2. B도둑이 훔치는 경우
cur_m + info[idx][1] < m이면 B도둑이 잡히지 않으므로 선택 가능하다.
Func(info, n, m, idx + 1, cur_n, cur_m + info[idx][1])
✅ 정답 코드
#include <string>
#include <vector>
#include <climits>
using namespace std;
vector<vector<vector<int>>> memo(40, vector<vector<int>>(121, vector<int>(121, -1)));
// A도둑이 남긴 흔적의 누적 개수의 최솟값을 return
int Func(vector<vector<int>> &info, int n, int m, int idx, int cur_n, int cur_m){
// base
if(idx==info.size()) return cur_n;
// recursive
// 이미 계산을 했다면 재계산X
if(memo[idx][cur_n][cur_m]!=-1) return memo[idx][cur_n][cur_m];
// A 도둑의 훔칠 경우
int tmp_a=INT_MAX;
if(cur_n+info[idx][0] < n) tmp_a=Func(info, n, m, idx+1, cur_n+info[idx][0],cur_m);
// B 도둑이 훔칠 경우
int tmp_b=INT_MAX;
if(cur_m+info[idx][1] < m) tmp_b=Func(info, n, m, idx+1, cur_n, cur_m+info[idx][1]);
return memo[idx][cur_n][cur_m] = min(tmp_a,tmp_b);
}
int solution(vector<vector<int>> info, int n, int m) {
int ans = Func(info,n,m,0,0,0);
return ans==INT_MAX?-1:ans;
}
⏱️ 시간복잡도 분석
메모이제이션을 사용하면 가능한 상태의 수만큼만 계산한다.
상태는 다음과 같다.
idx: 최대 40
cur_n: 최대 120
cur_m: 최대 120따라서 시간복잡도는 다음과 같다.
O(info.size() * n * m)최대값을 대입하면:
40 * 120 * 120 = 576,000이므로 충분히 통과 가능하다.
🏃♀️ 다른 코드 : 1차원 DP 풀이
이 문제는 3차원 메모이제이션 말고도 1차원 DP로 풀 수 있다.
핵심 아이디어는 다음과 같다.
dp[b] = B도둑의 흔적이 b일 때 가능한 A도둑 흔적의 최솟값즉, B 흔적을 기준으로 상태를 관리하고, 그때의 최소 A 흔적을 저장한다.
1. DP 상태 정의
dp[b]의 의미는 다음과 같다.
현재까지 물건을 훔쳤을 때,
B도둑의 흔적이 b이고,
그때 가능한 A도둑 흔적의 최솟값초기 상태는 아직 아무 물건도 훔치지 않았으므로 dp[0] = 0 이다.
2. DP 전이
각 물건마다 두 가지 선택을 한다.
1) A도둑이 훔치는 경우
A 흔적이 증가한다.
nextA = dp[b] + item[0]단, A가 잡히면 안 되므로 nextA < n 일 때만 가능하다.
2. B도둑이 훔치는 경우
B 흔적이 증가한다.
nextB = b + item[1]단, B가 잡히면 안 되므로 nextB < m 일 때만 가능하다.
1차원 DP 정답 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> info, int n, int m) {
const int INF = 1e9;
vector<int> dp(m, INF);
dp[0] = 0;
for (auto item : info) {
int aTrace = item[0], bTrace = item[1];
vector<int> next(m, INF);
for (int b = 0; b < m; b++) {
if (dp[b] == INF) continue;
// A도둑이 훔치는 경우
int nextA = dp[b] + aTrace;
if (nextA < n) next[b] = min(next[b], nextA);
// B도둑이 훔치는 경우
int nextB = b + bTrace;
if (nextB < m) next[nextB] = min(next[nextB], dp[b]);
}
dp = next;
}
int answer = *min_element(dp.begin(), dp.end());
return answer == INF ? -1 : answer;
}✨ 요약
| 알고리즘 | 핵심 아이디어 | 시간복잡도 |
| 완전탐색 | 모든 물건에 대해 A/B 선택을 전부 탐색 | O(2^N) -> 모든 경우의 수 |
| 메모이제이션 | (idx, A흔적, B흔적) 상태를 저장해 중복 계산 제거 | O(N * n * m) -> 가능한 상태 수 만큼 |
| 1차원 DP | dp[B흔적] = 가능한 A흔적의 최솟값으로 관리 | O(N * m) |