문제 출처 - https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW5jNL968dwDFATQ
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 요약
마트에 N봉지의 과자가 일렬로 나열되어 있고, 이 중 i번째 봉지는 Ai개의 조각을 가지고 있다.
추가적으로 M개의 봉지가 더 제공되며, 이 중 i번째 봉지는 Bi개의 조각을 가지고 있다.
일렬로 나열된 N개의 봉지의 과자 사이에 M개의 봉지를 아무 곳에나 끼워 넣을 건데, N개의 봉지는 초기 순서를 유지하고 있어야 한다.
이때 우리는 좌에서 우로 순서대로 걸어가며 과자를 뽑아가는데, 과자 한 봉지를 가져갔다면 그 다음 과자 봉지는 절대 가져갈 수 없다.
가져갈 수 있는 과자 조각의 최댓값을 구하면 된다.
풀이
AC를 받을 수 있는 풀이를 설명하기에 앞서, 내가 처음에 떠올렸던 못 받을만한 풀이법 몇가지를 짚고 넘어가겠다.
우선 필자는 처음 문제를 봤을 때, 어떤 물체를 선택할 지 선택하지 않을 지에 대한 최대,최소값을 구하는 문제라서 바로 익숙한 dp 문제라 생각을 하고 문제 풀이에 들어간 상태라고 생각하고 읽어보면 더 좋을 듯하다.
1) Brute-force + dp
이 풀이 방법은 Brute-force 방식으로 M 봉지의 과자를 사이사이 배치하고, 그 모든 경우의 수 마다 dp로 돌리는 것이다.
예상되는 dp table은 dp[idx][get] : 현재 idx 봉지를 get(0 or 1) 한 경우 과자 조각의 최댓값이다.
단순하게 M 봉지의 과자를 사이사이 배치하는 경우의 수가 너무 많기때문에 불가능하다는 것을 쉽게 알 수 있다.
2) Greedy + dp
말 그대로 그리디하게 M개의 봉지를 적절히 배치한 후 위 방식처럼 dp를 돌리는 방식이다.
N개의 봉지들 중 가장 과자조각이 적은 봉지들 옆에 M개의 봉지들 중 가장 과자조각이 많은 봉지들을 놓게된다면, 상대적으로 과자조각이 많은 봉지들을 집어가게 될 확률이 높기 때문에 이득을 볼 수 있다.
하지만 만약 모든 M개의 봉지들에 들어있는 과자조각이 모든 N개의 봉지들에 들어있는 과자조각보다 적다면, 또는 M개의 봉지들에 들어있는 과자조각이 훨씬 많다면 반대로 N을 M에 붙이는 식의 방법을 생각해봐야 할 것이다. 아무튼 이런 이유로 그리디한 풀이도 불가능하다고 판단했다.
3) dp
정답 풀이이다.
추가해야 할 봉지의 수 M이 생각보다 많이 작다는 점에서 착안해 어떻게하면 메모이제이션을 할 수 있고, 이걸 계속 사용할 지 생각해보았고 처음에 생각한 dp table은 다음과 같다.
dp[n_i][start_m][end_m][get] : 현재 n개의 봉지들 중 n_i번째 봉지를 보고 있고, 이 사이에(n_i ~ n_i + 1) [start_m, end_m] 구간의 m개의 봉지들을 집어 넣는 경우, 그리고 이때 봉지를 집은 경우(get) 과자 조각의 최댓값
우걱우걱 대충 메모리 맞게 dp table을 만들긴했는데.. [start_m, end_m] 구간의 경우의 수가 유니크하지 않기 때문에 불가능한 방법이었다.
그래서 두 번째로 생각한 방법은 "기왕 m개의 봉지를 선택할꺼면, 최대값부터 내림차순으로 선택하고 나머지는 스킵하는 걸로 카운팅을 하면 어떨까?" 라는 것이었다. 해당 dp table은 다음과 같다.
dp[n_i][m_i][skip][get]
- n_i : n봉지의 과자 중 n_i번째를 보고있는 상태(0과 n은 각각 왼쪽 끝, 오른쪽 끝을 의미한다)
- m_i : 내림차순으로 정렬된 m봉지의 과자 중 고른 과자의 수
- skip : m봉지 중 스킵한 개수
- get : 위 상태일 때 바로 직전에 과자를 get했는가 (했으면 1)
이 table 대로라면 배열의 원소가 같을 때(상태가 똑같을 때) 항상 최댓값이 똑같을 것이라 생각했고, 재귀적으로 구현했더니 AC를 받을 수 있었다.
정답 코드(.cpp)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;
//dp[n_i][m_i][skip][get]
//n_i : n봉지의 과자 중 n_i번째를 보고있는 상태(0과 n은 각각 왼쪽 끝, 오른쪽 끝을 의미한다.
//m_i : m봉지의 과자 중 고른 과자의 수
//skip : m봉지 중 스킵한 개수
//get : 위 상태일 때 바로 직전에 과자를 get했는가 (했으면 1)
int dp[3001][101][101][2];
vector<int>vn, vm;
int n, m;
int go(int n_i, int m_i, int skip, int get){
//만약 n봉지 끝까지 갔고 && m봉지도 끝까지 간 경우(고른 과자 + 스킵 과자)
if(n_i == n && m_i + skip == m) return 0;
int &ret = dp[n_i][m_i][skip][get];
if(ret != -1) return ret;
ret = 0;
//고르지 않은 경우
if(get == 0){
//만약 n봉지를 다 고르지 않은상태일때
if(n_i < n){
ret = max(ret, go(n_i + 1, m_i, skip, 1) + vn[n_i]); //고르거나
ret = max(ret, go(n_i + 1, m_i, skip, 0)); //고르지 않거나
}
//만약 m봉지를 다 고르지 않은상태일때
if(m_i + skip < m){
ret = max(ret, go(n_i, m_i + 1, skip, 1) + vm[m_i]); //고르거나
ret = max(ret, go(n_i, m_i, skip + 1, 0)); //고르지 않거나
}
}
//이미 고른 경우 -> 어디를 스킵할까?
else{
//만약 n봉지를 다 고르지 않은상태일때
if(n_i < n){
ret = max(ret, go(n_i + 1, m_i, skip, 0)); //고르지 않거나
}
//만약 m봉지를 다 고르지 않은상태일때
if(m_i + skip < m){
ret = max(ret, go(n_i, m_i, skip + 1, 0)); //고르지 않거나
}
}
return ret;
}
int main(int argc, char** argv) {
int t; cin>>t;
int num = 1;
while(t--) {
cin>>n;
vn.resize(n+1);
for(int i=0; i<n; i++) cin>>vn[i];
cin>>m;
vm.resize(m+1);
for(int i=0; i<m; i++) cin>>vm[i];
vm[m] = -987654321;
sort(vm.begin(), vm.end(), greater<int>());
memset(dp, -1, sizeof(dp));
cout<<"#"<<num<<" "<<go(0, 0, 0, 0)<<"\n";
num++;
}
return 0;
}