코딩테스트/동적계획법

[DP] 백준 7579 앱 C++

유(YOO) 2022. 1. 27. 12:24

 

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

 

7579번: 앱

입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활

www.acmicpc.net

 

#include<iostream>
#include<vector>
#define INF 1234567891
using namespace std;

int n, m, a, ans=INF, sum;
int dp[101][10001];
vector<int> M;
vector<int> C;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;

    C.push_back(0);
    for (int i = 0; i < n; i++) {
        cin >> a;
        M.push_back(a);
    }

    M.push_back(0);
    for (int i = 0; i < n; i++) {
        cin >> a;
        C.push_back(a);
        sum += a;
    }

    for (int j = 0; j < sum + 1; j++) {
        for (int i = 1; i < n + 1; i++) {
            if (j >= C[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - C[i]] + M[i - 1]);
            else dp[i][j] = dp[i - 1][j];
            
            if (dp[i][j] >= m) {
                ans = min(ans, j);
                break;
            }
        }
    }

    cout << ans;
}