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

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

 

 

이 문제는 공부할 수 있는 총 시간이 주어지고, 각 단원에 대해 얻을 수 있는 점수와 공부해야하는 시간이 주어진다.

이때 각 단원을 선택해서 총 시간안에 공부했을때 최대 점수를 출력하는 문제이다.

 

문제를 읽다보면 0-1 knapsack 문제랑 거의 유사하다는 느낌을 많이 받았다.

 

 

knapsack 문제에서 중요한건 최대무게를 0에서부터 1씩 늘려가며 담을 수 있는지 없는지 판단하는 것이 중요하다.

 

 

 

위 사진을 보자 편의상 S배열은 들을 수 있는 단원이며 얻을 수 있는 점수와, 공부해야하는 시간이 같으며

T는 총 시간으로 총 12시간동안 공부할 수 있다고 가정해보자

 

위 그림에서 2차원 배열을 살펴보면 행은 등을 수 있는 단원 수로 구성되었으며 열은 총 시간을 나타낸 것이다.

 

아까 언급했듯이 knapsack(배낭 문제)에서는 무게를 1씩 늘려가며 담을 수 있는지 없는지 판단하는 것이 중요하다.

이 문제도 마찬가지로 총 시간을 1씩 늘리며 해당 단원을 공부할 수 있는지 없는지 판단해야 한다.

 

인덱스 0에서 보면 단원을 고려하지 않았기 때문에 최대 점수는 0이된다.

따라서 행과 열의 인덱스 0인 부분의 최대 점수는 다 0이 될 수 밖에 없다.

 

이제 행의 인덱스 1로 옮겨서 살펴보자

 

 

여기서는 S 배열의 요소가 2인것을 고려한다. -> 즉 이번 단원을 듣기위해 2시간이 필요하며 2의 점수를 얻을 수 있다.

T가 1인 경우 총시간이 1이기 때문에 들을 수 없다 따라서 이전에 값을 그대로 가져온다.

 

그 이유는 이번 단원을 들을 수 없기 때문에 이번 단원은 고려하지 않겠다는 것이다 따라서 이전까지 고려했던 단원의 최대 점수를 가져오는것이다.

 

 

이제 T가 2인 경우를 보자

 

총 시간이 2이기 때문에 이번 단원은 들을 수 있다. 그렇기 때문에

이전값을 가져온는 것과 총 시간에서 이번 단원의 소요 시간을 이전 값에서 빼주고 현재 단원 점수를 더해주는 것과 비교를 해준다.

 

이전 값을 가져오는 이유는 만약 S 배열이 2, 3, 4가 아닌 3, 2, 4라고 가정을 한다면

{2,2} 에서의 값이 3이여야 하는데 2가 될 것이다. 따라서 이전값을 가져오는게 더 크다면 가져오는 것이고

 

dp[i-1][j-S[i]] + s[i] 는 

이전 상태 + 현재 물건을 넣는 것이다.

즉 "이전까지 고려한 물건(i-1번째까지)으로, 현재 배낭 용량에서 S[i]만큼 뺀 용량을 채우는 최대 가치에다가 지금 물건 S[i]의 가치를 더한 것"을 고려한 최대 값이라는 것이다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {0, 1, -1, 0, 1, -1, -1, 1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int N, T, result;
int weight[101];
int value[101];
int dp[101][10001];

void solve() {
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= T; j++) {
            if(weight[i] > j) {
                dp[i][j] = dp[i-1][j];
                result = max(result, dp[i][j]);
            }
            else {
                dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]]);
                result = max(result, dp[i][j]);
            }
        }
    }

    cout << result;
}

void input() {
    cin >> N >> T;

    for(int i = 1; i <= N; i++) {
        int a, b;
        cin >> a >> b;
        weight[i] = a;
        value[i] = b;
    }

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

이러한 배낭 문제를 1차원 배열을 사용하여 풀 수도 있다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {0, 1, -1, 0, 1, -1, -1, 1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int N, T;
int dp[10001];
vector<pii> v;

void solve() {
    for(auto it : v) {
        int times = it.first;
        int score = it.second;

        for(int j = T; j >= times; j--) {
            dp[j] = max(dp[j], dp[j-times] + score);
        }
    }

    cout << dp[T];
}

void input() {
    cin >> N >> T;

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}