문제설명
문제에 대한 접근은 특정 값을 구성하기 위해서 각각의 가중치를 가진 다른 종류의 선택지들을 어떻게해야 최대한의 가중치를 가지면서 구성할 수 있는가로 접근을 하면 되기 떄문에 바로 DP 중에서도 Knapsack 방식으로 풀이하면 된다고 접근할 수 있었다. 다만 문제에서 까다롭게 요구하는 부분이라면 단순한 방식으로 [선택지의 종류] * [구성하려는 가중치의 값]의 배열로 DP를 선언하게 되면 메모리 초과가 발생한다는 점이다.
140MB으로 메모리 초과!!
따라서 이를 효율적으로 메모리를 사용하면서 DP를 접근하는 방식이 필요한데 이에 대한 아이디어는 이전에 풀었던 백준 9084 동전문제에서 얻어올 수 있다. 이전 종류에서 얻어진 값은 어차피 그대로 다음 종류에서 그대로 활용을 하게 되기 때문에 굳이 종류의 가지 수 만큼 행을 선언하는 것이 아니라 일차원으로 DP를 선언하고 이를 선택지의 종류 수만큼 반복문을 돌려가면서 업데이트 해주는 방식으로 접근하는 것이다.
하지만 동일한 방식이라 하더라도 이번 문제와는 차이점이 있는데 동전 문제의 경우에는 한 종류의 동전을 여러번 반복해서 사용할 수 있었으나 이번 문제에서는 수도관을 한번씩만 사용해서 구성하는 것이다. 이런 경우에 발생하게 되는 문제점은 이번에 살펴볼 수도관을 넣을지 말지는 결정하는데 반복 여부를 확인할 수 없다는 문제점이 발생한다.
수도관 3 짜리를 넣어야할지를 결정한다고 봤을 때
1,2에서는 값이 길이보다 작으므로 skip하지만 3에서는 뺀 값이 0이고 dp[0]은 딱 맞아떨이지는 경우를 위해서 가능하다고 보게 설정하므로 가능하다고 본다.
이렇게 되면 문제점은 나중에 길이 6에서 체크를 할 때 3을 뺀 3의 값이 가능하다고 말하므로 6도 그 값을 기반으로 가능하다고 판단하게 되는 것이다. 사실 3은 자기자신을 넣었던 것이므로 불가능한 상황인데말이다.
이를 해결하기 위한 접근법으로 일반적으로 이전 상태 dp값과 현재 상태 dp값을 따로 잡아서 일차원DP를 2개 사용하여 접근할 수 있다.
이번에 운이 좋게도 조금 다른 방식으로 접근했어서 이를 소개하자면 내가 현재 사용되지 않은 경우들만 체크하기 위해서 인덱싱을 작은 값부터 시작하는 것이 아니라 큰 값부터 시작해서 내려오는 것이다. 일차원 DP로 계속 업데이트해서 사용하기 때문에 한 종류를 시작하기 전에 받은 초기의 DP값은 이전 종류에서 가능했던 값을 저장해놓은 상태이다. 따라서 자기자신을 제외하고 구성될 수 있는 숫자에다가 자신을 더한 값들만 경우를 체크하게 되는 이전의 문제 상황을 해결할 수 있다.
앞선 예시를 다시 보자면 6에서부터 시작해서 3을 빼보면 현재는 구성된 값이 없으므로 불가능하다고 판단하고 넘어가고 3에 와서는 나누어 떨어지는 경우이므로 가능하다고 생각해서 DP값을 업데이트한다.
아주 간단한 아이디어를 적용해서 일차원 DP 배열 하나로 문제를 풀 수 있게 됐다.
C++ 코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("inp.txt", "r", stdin);
int D, P;
cin >> D >> P;
vector<int> dp(D+1, 0);
dp[0] = 1;
// Kanpsack + 2to1DP
for(int i=1; i<=P; i++){
int L, C;
cin >> L >> C;
// 인덱싱 큰 쪽에서부터 내려와야 하나의 파이프라인 중복적으로 사용 안 할 수 있음
for(int j=D; j>=L; j--){
if(dp[j-L]){
if(j==L)
dp[j] = max(dp[j], C);
else
dp[j] = max(min(dp[j-L], C), dp[j]);
}
}
}
cout << dp[D];
}
