백준 14728번 벼락치기 C++

문제

 

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

---

Algorithm

전형적인 배낭 문제이다.

dp[i][j] : i번째 단원까지 고려했을 때, 총 공부 시간이 j일때 얻을 수 있는 최대 점수

점화식 : dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second

- dp[i - 1][j]는 i번째 단원을 선택하지 않는 경우, i번째 단원을 고려하지 않고 이전 단원까지의 최대 점수
- dp[i - 1][j - v[i].first] + v[i].second는 i번째 단원을 공부하기 위해 필요한 시간 v[i].first가 j보다 작거나 같은 경우에만 가능하다. 선택하는 경우에는 해당 단원을 선택하기 전까지의 최대 점수에 현재 단원의 점수를 더한다.

이후 dp[n][t]를 출력하면 답안이 된다.

---

Code

#include <bits/stdc++.h>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

int dp[101][10001];
int n, t;
vector<pii> v;

void INPUT()
{
    IAMFAST
    cin >> n >> t;
    v.emplace_back(0, 0);
    for (int i = 0; i < n; i++)
    {
        int k, s;
        cin >> k >> s;
        v.emplace_back(k, s);
    }
}

void solution()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= t; j++)
        {
            if (j - v[i].first < 0) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second);
        }
    cout << dp[n][t];
}

int main()
{
    INPUT();
    solution();
}