문제설명
접근방식
이번 문제는 이전에 썼던 글의 연속성 속에서 쉽게 어떤 문제인지 예측해볼 수 있다.
문제 1
문제 2
앱에서 실행 중인 앱들을 비활성화해서 원하는 메모리 공간의 크기를 확보해줘야 하는데 이는 다양한 종류의 값과 가중치를 가진 옵션들을 선택해서 특정 가중치 값안에서 최고 혹은 최소의 값을 찾아내는 문제인 것이다. 자연스럽게 원하는 배나에 주어진 무게 안에서 얼만큼 최대한 값어치 높게 담을 수 있을지는 해결해주는 DP Knapsack 문제로 접근할 수 있다. 그리고 이 알고리즘의 접근 방식에 대해서 위 링크로 남긴 이전 문제들에서도 풀어봤었다. 흥미로운 점은 저 문제들이 일정한 연관성 속에서 조금씩 신경써야 하는 부분들이 추가로 발생하고 있다는 것이다.
문제 1 접근
우선 문제1에서는 기본적인 Knapsack 개념을 가져와서 적용하는 문제였다. 다만 여기서 추가된 부분은 한 종류의 동전을 반복적으로 사용할 수 있다는 점에서 어차피 이전 종류에서 얻었던 DP값이 다음 종류에서 default값으로 깔려있고 이를 바탕으로 새로운 DP 값을 업데이트해야 하다보니 효율적인 코딩의 방식으로는 일차원 DP배열을 선언해서 종류 수만큼 반복적으로 업데이트하는 방식으로 접근하는 것이다.
문제 2 접근
다음 문제2에서는 저 개념에서 일단 기본적으로 메모리 제한이 걸리게해서 (옵선의 종류 수) * (정해진 가중치)의 이차원 배열 형태로 풀이할 수 없게 만들었다. 여기서 풀이를 할 때 이전 상태를 기억하는 DP 배열 하나와 현재 상태를 잡는 DP배열 하나를 잡아서 풀 수도 있다. 그런데 위의 방식고 동일하게 일차원 DP 배열 하나만 잡아서 문제를 풀 수 있는데 이때 신경써야 하는 점은 한 종류의 옵션에 대해서 한번씩밖에 사용할 수 밖에 없기 때문에 이를 중복 사용하지 않는지 체크를 해주느 방법이 추가되어야 한다. 이를 인덱싱이 큰 값에서부터 내려오는 방식으로 DP 값을 업데이트해주게 반복문을 돌리면 자기 이전의 종류들만으로 현재 체크하고자 하는 값이 만들어지는지 확인하고 중복 없이 현재 옵션을 넣어서 구성 가능한지 확인 할 수 있다.
그렇다면 이번 문제에서는 어떤 점이 추가되었을까. 이번 문제에서는 Knapsack문제임을 변하게 하는 것은 아니지만 원하는 가중치 값의 한계가 한정적으로 딱 정해지는 것이 아니라 그것보다 더 큰 가중치를 가지게 해결하더라도 더 좋은 값의 구성을 만들어낼 수 있으면 좋은 선택이 된다는 점이 특이했다.
cout << DP[N]Knapsack 방식의 문제들은 저런 방식으로 가중치의 크기만큼 DP 배열을 잡아주고 최종적으로 마지막 인덱스의 값이 최종 DP의 값이 되기 때문에 저런 방식으로 답을 출력하게 되는데 이번 문제에서는 그렇지 않은 경우들도 발생하는 것이다. 예를 들어 정해진 가중치는 100인데 (60, 4) (50, 3)의 방식의 조합으로 답이 풀리게 되면 DP[110]의 값을 출력해줘야 하는 것이 된다. 그래서 DP의 크기를 잘 잡아주고 DP[M]에서부터 그 뒤까지의 값 중에서 가장 작은 값을 출력해주는 과정을 추가해야 한다.
성급하게 접근했던 것은 있지만 배열의 크기를 잘 잡아주는 부분에서 '틀렸습니다'를 많이 받았다. 가중치 한계 뒤에 있는 배열을 얼만큼 더 잡아줘야 하는 부분이 문제였던 것인데 핵심 접근은 마지막에 추가되는 옵션의 가중치는 최소한 한계값보다는 작다는 생각이었다. 왜냐하면 그렇지 않았다면 이미 가중치와 같거나 커서 걸렸을 것이므로. 그리고 옵션의 가중치가 갑자기 혼자 너무 크게 튀어버리는 경우도 발생할 수 있다. 이런 경우들을 다 고려해서 처리할 수 있게 옵션의 가중치를 입력받으면서 최대값을 구해주고 이를 가중치 한계값고 비교해서 더 큰 값의 2배 크기로 DP를 선언하고 이전에 사용했던 방식으로 DP 풀이르 진행했다. 그리고 정답 출력은 가중치 한계값에서부터 시작해서 배열의 끝까지 중에서 가장 작은 값을 골라서 출력해줬다.
C++ 코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair <int, int>;
#define INF 40000
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
freopen("inp.txt", "r", stdin);
int N, M;
cin >> N >> M;
vector<pii> arr(N+1);
int max_m = -1;
for(int i=1; i<=N; i++){
cin >> arr[i].first;
max_m = max(max_m, arr[i].first);
}
for(int i=1; i<=N; i++)
cin >> arr[i].second;
int SIZE = max(2*max_m+1, 2*M+1);
vector<int> dp(SIZE, INF);
for(int i=1; i<=N; i++){
for(int j=SIZE; j>=arr[i].first; j--){
if(j == arr[i].first)
dp[j] = min(dp[j], arr[i].second);
else if(dp[j-arr[i].first] != INF)
dp[j] = min(dp[j], dp[j-arr[i].first] + arr[i].second);
}
}
cout << *min_element(dp.begin()+M, dp.end());
}