[BOJ] 23748 - 방문 판매

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

BOJ - 방문 판매

문제 유형: 다이나믹 프로그래밍, 배낭 문제

문제 난이도: Gold II

시간 제한: 1초

메모리 제한: 1024MB

 

문제

SG그룹은 이번에 획기적인 제품 X, Y를 출시했다. SG그룹의 영업 부서에서 외판원으로 일하는 판매왕 레오는 이 두 제품을 주어진 각 할당량 X, Y만큼 N명의 고객의 집을 모두 방문하여 팔아야 한다. 고객마다 1번부터 N번까지 번호가 주어지고, i번 고객의 집에 방문하여 판매에 성공했을 때 팔 수 있는 제품 X, Y의 양이 각각 x_i, y_i로 주어진다. 그러나 어떤 고객은 방문하더라도 제품 구매를 거절하여 판매에 실패할 수 있다.

방문 판매를 할 때는 영업 부서에서 정한 매뉴얼에 따라 1번 고객부터 N번 고객까지 오름차순으로 한 번씩 방문해야 한다. 또한, 레오가 판매하면서 가지고 다니는 차에는 제품 X, Y가 부족할 일이 없도록 충분히 많은 양을 채운다.

레오는 이번 방문 판매로 최소 몇 명의 고객에게 두 제품 X, Y를 팔아야 주어진 할당량을 채울 수 있는지 궁금해졌다. 방문 순서를 만족하면서 할당량을 채우기 위해 제품을 구매하도록 만들어야 하는 최소 고객의 수와 이때 가장 마지막으로 판매에 성공하는 고객 번호를 구해보자.

 

입력

첫 번째 줄에 레오가 방문해야 하는 고객 수인 N과 판매해야 하는 두 제품 X, Y의 할당량인 X, Y가 정수로 주어진다. (1 <= N <= 50, 1 < X, Y <= 100)

 두 번째 줄부터 N개의 줄에 걸쳐 1번부터 N번 고객까지 각 고객을 방문하여 판매에 성공했을 때 해당 고객이 구입하는 두 제품 X, Y의 양인 x_i와 y_i가 정수로 주어진다. (1 <= x_i, y_i <= 100, 1 <= i <= N)

 

출력

방문 순서를 만족하면서 할당량을 채우기 위해 제품 판매에 성공해야 하는 최소 고객의 수를 출력한다. 이때 마지막으로 판매에 성공하는 고객의 번호를 그 다음 줄에 출력하는데, 가능한 번호가 여러 개이면 그중 가장 작은 값을 출력한다.

어떠한 고객이 제품을 구입한다고 하더라도 할당량을 채울 수 없는 경우에는 -1을 출력한다.

 

풀이

각 고객을 마지막 구매자 후보로 두고,

i번째가 마지막 고객이라 하면, 0 ~ i-1번째의 범위로 0-1냅색을 이용하여 dp[x][y]에 대한 필요한 최소 구매인원을 구한다.

 

그 뒤, targetX를 후보자 i가 사기 이전의 최소 x 구매량이라 하고, targetY도 그렇다고 할때, dp[targetX][targetY] ~ dp[X][Y]중에서 최소값을 구한다.

 

최소값이 기존보다 작다면, 구매자와 최소값을 업데이트한다.

 

최종적인 값을 반환하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int INF = 1e9;
int N, X, Y;

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> X >> Y;
    vector<pii> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i].first >> a[i].second;
    }

    int minCount = INF;
    int lastCustomer = -1;
    for (int i = 0; i < N; i++) {
        int targetX = max(0, X - a[i].first);
        int targetY = max(0, Y - a[i].second);

        vector<vector<int>> dp(X + 1, vector<int>(Y + 1, INF));
        dp[0][0] = 0;

        for (int j = 0; j < i; j++) {
            int xi = a[j].first;
            int yi = a[j].second;
            for (int x = X; x >= 0; x--) {
                for (int y = Y; y >= 0; y--) {
                    if (dp[x][y] == INF) continue;
                    int nx = min(X, x + xi);
                    int ny = min(Y, y + yi);
                    dp[nx][ny] = min(dp[nx][ny], dp[x][y] + 1);
                }
            }
        }

        int best = INF;
        for (int x = targetX; x <= X; x++) {
            for (int y = targetY; y <= Y; y++) {
                best = min(best, dp[x][y]);
            }
        }
        if (best != INF) {
            int tot = best + 1;
            if (tot < minCount) {
                minCount = tot;
                lastCustomer = i + 1;
            }
        }
    }

    if (minCount == INF) {
        cout << "-1\n";
    } else {
        cout << minCount << "\n" << lastCustomer << "\n";
    }

    return 0;
}