[백준 / C++] 7579번: 앱

백준 7579번: 앱
알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제

백준 문제 바로가기

🤨 Hmm...

클래스 5+ 문제인데 배낭 문제라서 겁 먹고 문제 조차 안 보던 문제다.

이전에 배낭 문제 풀 때, 풀이를 보고도 잘 와닿지 않았었는데 지금까지 여러 DP문제들을 접해봐서 그런지 이제 이해가 가는 것 같다.

배낭 문제는 2차원 배열로 풀 수 있다.

DP[i][cost]는 1~i번째까지의 배낭을 고려했을 때 cost의 비용으로 얻을 수 있는 최대 가치를 의미한다.

cost[i]가 cost보다 크다면 DP[i-1][cost]를 그대로 가져와서 쓰면 되고,

그렇지 않다면 DP[i-1][cost](i번째 배낭을 선택하지 않은 경우)와 DP[i-1]cost-cost[i]] + value[i] 중 최댓값을 구하면 된다.

이 문제는 적어도 M바이트를 넘는 최소 비용을 찾아야 하기 때문에, 바이트 수를 value로 두고 풀면 된다.

근데 여기서 가치가 아니라 비용이 주 문제이기 때문에 가치가 M 이상일 때의 최소 비용을 구해주면 된다.

💻 소스 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <memory.h>
#define int long long
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int N, M;
    int A[101];
    int c[101];
    int DP[101][10001];
public:
    BJ();
    int solution();
};

BJ::BJ() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        cin >> A[i];
    for (int i = 1; i <= N; i++)
        cin >> c[i];

    cout << solution();
}
int BJ::solution() {
    int answer = INT32_MAX;
    memset(DP, 0, sizeof(int)*10001);
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < 10001; j++){
            if (c[i] > j)
                DP[i][j] = DP[i-1][j];
            else {
                DP[i][j] = max(DP[i-1][j], DP[i-1][j-c[i]] + A[i]);
                if (DP[i][j] >= M)
                    answer = min(answer, j);
            }
        }
    }
    return answer;
}

signed main(){
    fastIO;

    BJ Q7579;
}