[ 백준 14728 ] 벼락치기 (C++) - DP, KnapSack

---

🔗 문제 링크

14728번: 벼락치기

---

💡 문제 풀이 및 해석

1. 가치에 따라서 결정하는 냅색 문제이다.
2. 우리가 최대로 가져가야 하는 것은 점수이고, 그 비용은 시간이 된다.
3. 최대로 가져갈 수 있는 점수는 dp[T]에 있다. 이 때, 역순으로 다이나믹 프로그래밍을 진행한다.
4. dp는 그 시간대의 최대값이므로 검사할 시간이 t라면, dp[t] = max(dp[t], dp[t - time] + score)는 t-time 이 그 시간에서 최대이고 현재 값을 더하면 최대값인 dp[T]가 갱신될 수 있는지 확인하고 가능하면 확인하는 방식이다.
5. 모든 과목에 대해서 4번을 적용하면 얻을 수 있는 최대 점수가 나온다.

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>

using namespace std;

int N, T;
int dp[10001];
vector<pair<int, int>> lec; // 시간, 배점

void input() {
    cin >> N >> T;
    for (int i = 0; i < N; i++) {
        int K, S; cin >> K >> S;
        lec.push_back({ K,S });
    }
}

void sol() {
    for (int j = 0; j < N; j++) {
        int time = lec[j].first, score = lec[j].second;
        for (int i = T; i >= 0; i--) {
            if (time <= i) {
                dp[i] = max(dp[i], dp[i - time] + score);
            }
        }
    }
    cout << dp[T];
}

int main() {

    input();
    sol();

    return 0;
}

---

🤔 문제 후기

냅색 문제는 보통 이런식으로 풀기 때문에 어느정도 풀이 방식을 알고 있었다. DP문제는 풀어본 유형이 아니라면 아직은 풀기가 많이 힘들 것 같다.