[BOJ/Gold 5] 백준 29704 벼락치기(C++)

문제 링크

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

29704번: 벼락치기

 

문제

숙명여자대학교의 알고리즘 학회 ALGOS에 합격한 혜민이는 너무 기뻐 마음이 들뜬 나머지 프로그래밍 과제가 있는 것을 잊어버리고 말았다. 프로그래밍 과제로는 다양한 난이도의 문제 N개가 주어지고, 앞으로 T일의 제출 기한이 남아있다. 만약 제출 기한 내에 문제를 제출 못 하면, 제출하지 못한 문제마다 정해져 있는 벌금을 내야 한다. 혜민이는 벌금을 내고 싶지 않기 때문에, 내는 벌금의 총금액이 가능한 한 적어지도록 문제를 풀려고 한다.

문제를 해결하는 데 소요되는 일수와 그 문제를 제출 기한 내에 해결하지 못할 경우 내야 하는 벌금이 주어질 때, 혜민이가 내야 하는 벌금의 최소 금액을 구해보자. 제출 기한 T일이 지났을 때, 제출하지 못한 문제별 벌금의 합이 혜민이가 최종적으로 내야 하는 벌금이다. 단, 혜민이는 아직 프로그래밍에 익숙하지 않아서 한 번에 한 개의 문제만 해결할 수 있다.

 

	해결하는 데 소요되는 일수	벌금
문제1	2	5000
문제2	1	1000
문제3	1	2000

 

예를 들어, 프로그래밍 과제로 위와 같이 3개의 문제가 주어졌다고 가정해 보자. 제출 기한이 3일 남았다면, 첫째 날에 3번 문제를 해결하고, 둘째 날과 셋째 날에 걸쳐 1번 문제를 해결하면 2번 문제의 벌금인 1,000원만 내면 된다.

혜민이가 가능한 한 적은 벌금을 낼 수 있게 도와주자.

 

입력

첫째 줄에 문제의 개수 N(1 ≤ N ≤ 1,000)과 남은 제출 기한 T(1 ≤ T ≤ 1,000)가 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 i번 문제를 푸는 데 걸리는 일수 di(1 ≤ di ≤ 1,000)와 해당 문제의 벌금 mi(1 ≤ mi ≤ 5,000)이 주어진다.

 

출력

최종적으로 내는 벌금이 최소가 되도록 문제를 풀었을 때, 혜민이가 내야 하는 벌금을 출력한다.

만약, 기한 내에 모든 문제를 해결할 수 있다면 0을 출력한다.

 

예제 입력 1

3 3
2 5000
1 1000
1 2000

예제 출력 1

1000

 

예제 입력 2

4 5
2 5000
2 2000
2 3000
3 1000

예제 출력 2

3000

예제 입력 3

3 6
1 1000
2 4000
3 2000

예제 출력 3

0

 

알고리즘 분류

• 배낭 문제

 

풀이

T일동안 문제를 해결하고 최소한의 벌금을 물기 위해서는 해결한 문제의 벌금의 총합이 최대여야 한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, T, SumM;
int D[MAX], M[MAX];
int DP[MAX][MAX];
int Answer;

void input() {
    cin >> N >> T;
    for (int i = 1; i <= N; i++) {
        cin >> D[i] >> M[i];
        SumM += M[i];
    }
}

int top_Down(int Depth, int Day) {
    if (Depth == 0) {
        return 0;
    }

    if (DP[Depth][Day] != 0) {
        return DP[Depth][Day];
    }

    int Result = top_Down(Depth - 1, Day);
    if (Day - D[Depth] >= 0) {
        Result = max(Result, top_Down(Depth - 1, Day - D[Depth]) + M[Depth]);
    }

    return DP[Depth][Day] = Result;
}

void settings() {
    Answer = SumM - top_Down(N, T);
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}