BOJ 14728 : 벼락치기

www.acmicpc.net/problem/14728

14728번: 벼락치기

이 문제는 설명할 필요가 없다.

 

그냥 배낭 dp문제이다. 그러니까 그냥 하면 된다.

#include <bits/stdc++.h>
#define MEM 300009
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll n,m;
ll dp[102][10002];
int main() {
    sanic; cin.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        ll w,v;
        cin >> w >> v;
        for(int j=1; j<=m; j++){
            if(w>j) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v);
        }
    }
    cout << dp[n][m];
}