[백준 14728번] 벼락치기 (C++)

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

14728번: 벼락치기

배낭 문제랑 똑같은 문제이다.

배낭문제는 2차원 Dp를 이용해서 Buttom-up으로 풀었었는데 배낭문제는 1차원 Dp를 이용하면서 Top-down으로 풀어주는게 더 효율적이다.

배낭문제를 풀어본 사람이라면 알다시피 2차원 배열에서 굳이 값을 채우지 않아도 되는 배열까지 값을 채우기 때문에 메모리와 시간이 Top-down에 비해 오래걸린다.

 

주어진 시간이 Dp배열의 크기가 되고 안에 배점 S를 채우면 된다.

i는 1번째 단원부터 i번째 단원을 공부하여 얻을 수 있는 최대 배점이다.

j는 주어진 시간 - 소모되는 시간 > 0 일때까지 dp값을 갱신할 수 있다.(뒤에 필요없는 부분까지 할 필요 없음)

 

코드는 다음과 같다.

#include <iostream>
using namespace std;
int main(){
    int n,t;
    cin >> n >> t;
    int k[102];
    int s[102];
    int dp[10001] = {0,};

    for(int i = 1; i < n+1; i++){
        cin >> k[i] >> s[i];
    }
    
    for(int i = 1; i < n+1; i++){
        for(int j = t; j >= k[i]; j--){
            dp[j] = max(dp[j],dp[j-k[i]]+s[i]);
        }
    }
    cout << dp[t];
}