백준 14728번 벼락치기[골드 5][C++]

1. 개요

 안녕하세요. 이 문제의 유형은 0-1배낭 문제(knapsack problem)입니다. 문제 설명을 읽어보시면 전형적인 배낭 문제임을 알 수 있습니다. 로직 구현도 응용이 필요하지 않아 어려움이 없습니다. 배낭 문제 입문용으로 풀이하기 좋아 보였습니다. 저는 복습용으로 좋았습니다.

 

2. 문제 풀이

 DP 테이블 d[i][j] = k를 정의했습니다. i는 [1, i] (i <= N)까지의 단원, j는 공부한 시간, k는 최대 점수를 의미합니다. 그다음 loop를 순회하면서 점화식(d[i][j] = max(d[i-1][j - a.X] + a.Y, a[i - 1][j])를 수행하면 풀이할 수 있습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, t;
vpi a;
int d[105][100'005];

int main() {
    fastio(nullptr, false);

    cin >> n >> t;
    vpi (n + 1).swap(a);
    for(int i = 1; i <= n; i++) {
        cin >> a[i].X >> a[i].Y;
    }

    for(int i = 1; i <= t; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[j].X <= i) {
                d[j][i] = max(d[j - 1][i - a[j].X] + a[j].Y, d[j - 1][i]);
            } 
            else {
                d[j][i] = d[j - 1][i];
            }
        }
    }

    cout << d[n][t];
}

4. 제출 결과