📌 알고리즘 - 백준 14728번 벼락치기 문제풀이

문제

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

문제풀이

문제를 요약하자면, 준석이가 공부할 수 있는 총 시간 $T$ 동안 적절하게 $K$ 시간 단원을 공부해서 $S$ 점수를 얻을 때 얻을 수 있는 최대 점수를 구하는 것이다.

배낭 문제의 정의를 적용하면 된다.

코드

#include <bits/stdc++.h>
#define endl '\n'
#define NMAX 110
#define TMAX 10010
#define KMAX 1010
#define SMAX 1010
using namespace std;

int N, T;
int dp[NMAX][TMAX];
int K[KMAX];
int S[SMAX];
int ans;

void Initialize() {
    memset(dp, 0, sizeof(dp));
    memset(K, 0, sizeof(K));
    memset(S, 0, sizeof(S));
}

void Input() {
    cin>>N>>T;
    for (int i = 1; i <= N; i++) {
        cin>>K[i]>>S[i];
    }
}

void Solution() {
    for (int i = 1; i <= N; i++) {
        for (int t = 0; t <= T; t++) {
            if (t - K[i] >= 0) {
                dp[i][t] = max(dp[i-1][t], dp[i-1][t-K[i]] + S[i]);
            } else {
                dp[i][t] = dp[i-1][t];
            }
            ans = max(ans, dp[i][t]);
        }
    }
    cout<<ans;
}

void Solve() {
    Initialize();
    Input();
    Solution();
}

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

    Solve();

    return 0;
}