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

문제링크 : https://www.acmicpc.net/problem/14728

14728번: 벼락치기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, T, K, S;
int dp[10001];
int dp2[10001];

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

    cin >> N >> T; // 갯수, 총 시간
    for(int i=1; i<=N; i++)
    {
        cin >> K >> S; //공부 시간, 배점
        for(int j=T; j>=K; j--)
        {
            dp[j] = max(dp[j], dp[j-K] + S); //배낭 알고리즘
        }
    }

    cout << dp[T];
}

총 시간 내에 주어진 시간으로 최대한의 배점을 구하는 문제이다.

내용을 보아 배낭 문제임을 알 수 있다.

 

j 시간 만큼 (dp[j]) 최대 배점이 얼마인지를 구해주면 된다.

두번째 반복문을 int j=K~T로 하였다가 조금 헤매게 되었다.

 

직접 내용을 출력해보니 int j=K부터 시작할 경우에는 이미 푼 문제에 대해서 다시 풀어서 배점을 재획득하는 것을 반복하는 것을 알 수 있었다. (dp[300] = dp[50] * 6)

이를 위해서 dp[j]=T부터 시작하여 위에서부터 채워주도록 해주어야한다.