[백준] 7579 앱

배낭 관련된 문제들을 풀때 2차원 배열에 어떤 값을 넣어야 풀 수 있는지 아직 감이 잡히지 않는 것 같다.

 

배낭 유형 문제들을 풀면서 감을 익혀야 할 것 같다.

문제 - 1 페이지

 

 

이번 문제도 삽질을 좀 많이 했다..

2차원 배열에서 행: 입력 횟수, 열: 비용으로 생각하고 풀면 되지만

열에 해당하는 최댓값은 입력받은 모든 비용의 합으로 해야한다.

 

#include <bits/stdc++.h>
#define BYTE 1
#define COST 0

using namespace std;

void app7579(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N,M;
    cin>>N>>M;

    vector<pair<int,int>> App(N+1);
    int dp[N+1][10001];
    int allCost = 0;
    
    for(int i=1;i<=N;i++)
        cin>>App[i].first;
    for(int i=1;i<=N;i++){
        cin>>App[i].second;
        allCost += App[i].second;
    }
    for(int i=0;i<=N;i++)
        for(int j=0; j<=101; j++)
            dp[i][j] = 0;

    int minCost = INT_MAX;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=allCost; j++){
            if(j- App[i].second >= 0){
                dp[i][j] = max(dp[i-1][j], App[i].first + dp[i-1][j- App[i].second]);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
            if(dp[i][j] >= M) minCost = min(minCost,j);
        }
    }

    cout<<minCost<<endl;
}