[BOJ] 14728 번 - 벼락치기

백준 14728번 - 벼락치기

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	2088	874	673	41.723%

문제

ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.

1. 여러 단원을 융합한 문제는 출제하지 않는다.
2. 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.

이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정하자. 이때, ChAOS 회장 일로 인해 힘든 준석이를 위하여 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 프로그램을 만들어 주도록 하자.

입력

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과 시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와 그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 준석이가 얻을 수 있는 최대 점수를 출력한다.

---

예제 입력 1

3 310
50 40
100 70
200 150

예제 출력 1

220

출처

www.acmicpc.net/problem/14728

14728번: 벼락치기

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

접근 방법

위 문제를 해결하기 위해 가장 쉽게 떠올릴 수 있는 방법으로는 가능한 모든 경우를 다 따지는 것이다.

for문으로 i번째 task를 처리할지?/말지? 를 결정하는 2가지 방법이 문제의 개수인 N개가 존재하므로, 시간 복잡도는 $O(2^n)$ 이 될 것이다.

 

이것을 dynamic programming 을 통해 $O(N^2)$으로 줄일 수 있다.

그것이 바로 유명한 knapsack problem 이다.

이 문제의 유형은 쪼갤 수 없는 0/1 knapsack problem이다.

 

우리가 찾고자 하는 답이 특정 조건을 만족하는 최적해라면 memoization을 통해 문제를 해결할 수 있다.

위 문제에서 DP를 다음과 같이 정의해보자.

DP[i][j] = i번째 문제까지 확인했을 때, j시간 내에 얻을 수 있는 최대 점수

2차원 배열로 구현한 이유는 0/1 knapsack problem의 특성 상 모든 경우를 확인하지 않고, 각 단계별로 최적이 될 수 있는 후보해들만 고려해주는 것이기 때문이다.

 

DP[i][j]의 최적해가 될 수 있는 최적해는 2가지 경우 중 하나 이다.

1. 이전 작업(i-1) 까지만 고려했을 때, j시간 내에 얻을 수 있는 최대 점수

2. i번째 문제를 풀 수 있는 경우, i-1까지 고려했던 문제들 중 j시간내에 얻을 수 있었던 최대 점수 + 현재 문제의 점수 

위의 식을 다음과 같은 점화식으로 표현할 수 있다.

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N, T;
vector<int> req_time, score;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> T;
    req_time.resize(N), score.resize(N);

    for(int i=0; i<N; i++){
        cin >> req_time[i] >> score[i];
    }

    /// dp[i][j] : i번째 작업까지 확인했을 때, j시간 내에 얻을 수 있는 최대 점수
    int dp[101][100001] = {0,};
    for(int i=req_time[0]; i<=100000; i++)
        dp[0][i] = score[0];

    for(int i=1; i<N; i++){
        int t = req_time[i], s = score[i];
        for(int j=1; j<=100000; j++){
            if( j - t >= 0 ){
                dp[i][j] = max(dp[i-1][j-t] + s, dp[i][j]);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }

    cout << dp[N-1][T];

    return 0;
}