(C++) - 백준(BOJ) 14728번 : 벼락치기

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

14728번: 벼락치기

dp문제였습니다.

 

 

풀이방법

 1. d[i][j] = i시간동안 n번 챕터를 풀었을 때 얻을 수 있는 점수의 최댓값입니다.

 

 2. 점화식으로 나타내면 d[i][j] = 점수max(현재 챕터를 골랐을 때, 현재 챕터를 고르지 않았을 때)

입니다. 현재 챕터를 고르게 되면 현재 점수를 고른뒤 공부하는데 걸리는 시간을 빼주게 됩니다. 남은시간이 음수가 된다면 해당 공부법은 무효가 되므로 가장 작은 값을 반환합니다. 또한 n이 0인 기저 케이스의 경우에는 0을 반환합니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int chapterNum, studyTime;
vector <pii> info(101);
int d[10001][101];
int dp(int t, int n){
    if(t < 0) return -INF;
    if(!n) return 0;
    int &ret = d[t][n];
    if(ret != -1) return ret;
    ret = max(dp(t - info[n].first, n-1) + info[n].second, dp(t, n-1) );
    return ret;
}

int main() {
    memset(d,-1,sizeof(d));
    cin >> chapterNum >> studyTime;
    for(int i = 1; i <= chapterNum; i++)
        cin >> info[i].first >> info[i].second;
    cout << dp(studyTime, chapterNum);
}

 

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

 

5 349
50 40
60 30
70 20
80 10
90 5
답 : 100

5 349
50 40
60 5
70 20
80 1000
90 3000
답 : 4060

6 89
50 40
60 5
70 20
80 5000
80 1000
90 3000
답 : 5000

5 120
50 30
60 70
70 20
80 100
90 2000
답 : 2000

5 120
50 1001
60 1000
70 2000
80 100
90 2000
답 : 3001