[C++] 백준/BOJ - 14728 : 벼락치기

문제 이해 단계

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

14728번: 벼락치기

N개의 단원과 사용할 수 있는 총 시간 T가 입력으로 주어진다.

둘째 줄에는 각 단원에 대해서 공부하는데
걸리는 예상 시간과 배점이 입력으로 들어온다.

해당 조건에서 총 시간 T를 분배해서 각 단원을 공부하여
배점을 얻을 때 얻을 수 있는 최대 점수를 구하는 문제

 

---

문제 접근 단계

최대 점수를 구하는 문제라길래, 처음에는 그리디 문제가 아닌가 했다.
그런데 그리디 문제라면 지금 당장 선택한 것이 최적의 선택이 되어야 한다.

그런데 만약 예제케이스를 조금 변형해서

3 350

70 50
50 90
300 120

이런 상황에서 원래대로라면 최댓값은 140점이 된다.
그런데 만약 300 120을 먼저 발견했다고 가정하자.

이 값이 점수가 높기 때문에 먼저 넣으면 120이 최댓값이 되어버리는데,
이는 당장에 한 선택이 최댓값이 아니기 때문에 그리디를 만족하지 못한다.

 

---

시간 T를 다른 걸로 생각하기

그럼 그리디가 아니라면 어떻게 풀면 될까?

사실 시간 T를 조금만 다른 걸로 생각해 보면, 익숙한 문제가 된다.
시간 T는 소모되는 자원이자, 사용량이 한정되어 있다.

이걸 채워야 하는 공간이라고 생각해 보자.

즉 위의 예제에 따르면 T = 350은 350이라는 공간을 채워야 하는 것이다.
그리고 각 과목의 예상 시간은 그 공간을 채우는 물건이다.

이렇게 생각하면 익숙한 DP문제인 배낭문제와 완전히 똑같은 문제가 된다.

배낭 문제에 대해서는 아래에 정리한 글이 있기 때문에
아래 링크를 참고해 주길 바란다.

https://howudong.tistory.com/106

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

본인은 이걸 못 알아채서 결국 풀이를 참고했다.

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N;

// 과목을 나타내는 구조체
struct Subject{
    int t; // 예상 시간
    int s; // 배점
};


// 시간에 따른 오름차순 정렬
bool compare(Subject a, Subject b){
    return a.t < b.t;
}

// dp 배열
int d[101][10001] = {0,};

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T;
    cin >> N >> T;
    vector<Subject> v(N+1);
    for(int i = 1; i <= N; i++){
        int t,s;
        cin >> t >> s;
        v[i] = {t,s};
    }

    sort(v.begin()+1,v.end(),compare);

    int sTime = v[1].t; // 제일 작은 시간으로 최소 시간을 맞춤
    int ans = 0;

    // k = 각 과목
    for(int k = 1; k <= N; k++){
        // 최소 시간부터 시작
        for(int i = sTime; i <= T; i++){
            //d[k][i] = i시간까지 사용해서 k과목까지 탐색했을 때, 
            if(v[k].t > i) d[k][i] = d[k-1][i];
            else
            {
                d[k][i] = max(d[k-1][i],d[k-1][i-v[k].t]+v[k].s);
            }
            ans = max(ans,d[k][i]); // 최댓값을 구함
        }
    }
    cout << ans;
}

완벽한 기본적인 배낭문제이기 때문에 따로 설명은 크게 안 하겠다.

중간에 정렬을 해준 이유는,
dp의 시작 시간을 입력의 가장 작은 시간으로 맞춰주기 위함이다.

 

---

시행착오

센스가 너무 부족하다.

생각 조금만 다르게 하면 배낭문제인 거 바로 알 수 있는데 그걸 몰라서 못 풀었다.
배낭 문제는 풀 수 있는데 이 문제는 못 푸는 게 말이 안 된다.

진짜 ㅋㅋㅋㅋ..