[ boj : 2073 ] 수도배관공사

https://www.acmicpc.net/problem/2073

2073번: 수도배관공사

문제 : P개의 파이프가 주어지고 이것들을 잘 조합해서 길이 D의 수도관을 만들어야 합니다. 이때 수도관의 용량은 조합된 파이프들 중 가장 최소용량의 값이 됩니다. 이때 수고관의 용량의 최대값을 구하시오

해설 : 전형적인 DP 문제입니다. 다만 한눈에 해결방법이 전 보이지 않았습니다......
먼저 결국 길이 D의 수도관 중 가장 최소용량의 값을 구해야 되는 것이 정답이니 처음에 dp 배열을 2차원으로 새웠습니다.

$dp[i][j] = i 번째\ 파이프를\ 선택하려\ 하는\ 경우\ 길이가\ j이며\ 이때\ 수용할\ 수\ 있는\ 용량의\ 값$
그렇다면 x를 현재 선택하려는 파이프의 길이, y를 현재 선택하려는 파이프의 수용 용량 이라고 하면
$dp[i][j] = max(dp[i-1][j],min(dp[i-1][j-x],y)$ 가 됩니다.

그러나 이렇게 점화식을 세우면 문제가 발생합니다. 바로 메모리초과가 발생합니다.
주어진 조건은 128MB 이지만 dp 배열을 2차원으로 세워버린다면 즉, 공간복잡도 $O(DP)$ 로 선언을 한다면 128MB를 넘어버리게 됩니다.

우린 그럼 이 dp배열을 최적화를 시켜야 하는데, 바로 DP + 슬라이딩 윈도우 기법을 사용하면 됩니다.
예전 포스팅한 할로윈의 양아치(20303) 에서 적용한 기법 그대로를 여기서도 사용하면 됩니다.

탑-다운 방식의 dp 접근을 사용합니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int dp[(int)1e5+1];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int D, P;
    vector<pair<int, int>> v;
    cin >> D >> P;
    v.resize(P);
    for (int i = 0; i < P; i++)
        cin >> v[i].first >> v[i].second;
    dp[0] = (int)(1 << 24);
    for (int i = 0; i < P; i++)
        for (int j = D; j >= 0; j--) {
            if (j - v[i].first < 0)continue;
            dp[j] = max(dp[j], min(dp[j - v[i].first], v[i].second));
        }
    cout << dp[D];
    return 0;
}