[BOJ 1106] 호텔

배낭 문제

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

 

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

해당 문제를 응용한 문제입니다.

 

---

[문제 풀이]

 

전형적인 배낭 문제입니다.

적어도 C명을 늘리기 위한 최소한의 비용을 내야 합니다.

이 '적어도'가 중요하지만 지금은 넘어가겠습니다.

 

 

근본적인 해결 방법은 배낭 문제(다이나믹 프로그래밍)와 같습니다.

부분 문제로 나눠주면서 메모이제이션을 적용하면 됩니다.

 

한 개의 도시에 대해 할 수 있는 선택지는 다음과 같습니다.

    1. 해당 도시에 홍보를 한다. (홍보 비용을 지불하고 고객 수를 늘림)

    2. 해당 도시에 홍보를 하지 않는다. (홍보 비용을 지불하지 않음)

 

1번 선택지를 고른다면 해당 도시에 홍보 비용을 지불하기 전에 유치한 고객 대비 사용한 비용에 대한 최적해가 필요합니다.

2번 선택지를 고른다면 기존 최적해를 가져가면 됩니다. 

 

도시 하나씩을 살펴보면서 위 2가지 선택지 중 최선의 선택을 하여 dp테이블에 최적해를 채워 나가면 됩니다.

 

※ 최소한의 비용을 찾는 문제이므로 min함수를 사용합니다. 즉 dp테이블의 초기값을 큰 수로 지정해야 합니다.

1000명을 늘려야 하고 1명당 100만큼을 지불하는 경우가 최악의 경우이고, 그러므로 100000이 최대 비용입니다.

초기값이 100000보다 크기만 하면 됩니다.

 

 

이해를 돕기 위해 2번 예제로 예시를 들겠습니다.

 

초기 상태

초기 상태는 현재와 같습니다.

 

i가 0인 부분만 0인 것은 일종의 테크닉입니다.

1번 선택지를 점화식으로 바꾸면 dp[i] = dp[i - 현재 도시 고객] + 현재 도시 비용이 됩니다. dp[0] = 0으로 초기화함으로써 i - 현재 도시 고객 == 0인 경우 dp[i] = dp[0] + 현재 도시 비용이므로 dp[i] = 현재 도시 비용으로 바로 설정할 수 있게 됩니다.

이렇게 하지 않고 i - 현재 도시 고객 == 0인 경우에 대한 예외 처리를 해도 되지만, dp문제를 풀다 보면 i가 0인 부분을 얼마나 잘 활용하느냐가 코드 최적화에 큰 기여를 합니다.

 

첫 번째 도시 확인 후 (파란색 부분은 갱신된 값)

첫 번째 도시를 확인하였습니다. 최적해가 갱신된 부분은 파란색으로 칠했습니다.

 

첫 번째 도시이므로 당연히 모든 dp테이블이 갱신되었습니다. 여기서 갱신됐다는 것은, 해당 도시에 홍보를 했음을 나타냅니다.

 

두 번째 도시 확인 후 (파란색 부분은 갱신된 값)

두 번째 도시를 확인하였습니다. 최적해가 갱신된 부분은 파란색으로 칠했습니다.

 

두 번째 도시에서는 1명의 고객을 유치하는 경우는 불가능하므로 제외하고 모든 dp테이블이 갱신되었습니다.

 

세 번째 도시 확인 후 (파란색 부분은 갱신된 값)

세 번째 도시를 확인하였습니다. 최적해가 갱신된 부분은 파란색으로 칠했습니다.

 

세 번째 도시에서는 1, 2명의 고객을 유치하는 경우가 불가능하여 갱신되지 않았고, 4명의 고객을 유치하는 경우는 세 번째 도시에 홍보를 하지 않는 것도 최적해가 되므로 갱신하지 않았습니다.

 

 

확인을 마치고 보니 예제의 출력인 4가 나오지 않았습니다.

여기서 처음에 말했던 '적어도'의 필요성이 나옵니다.

 

이 문제는 정확히 C명을 유치하는 문제가 아닙니다. C명 이상이 C명을 유치하는 것보다 이득이라면 C명 이상을 유치하는 것이 정답입니다.

예제 2번 역시 세 번째 도시 (3 1)에서만 4번 홍보한다면 4만큼의 비용으로 12명을 유치할 수 있으므로 답은 4가 됩니다.

 

비용은 자연수이기에 많은 인원을 유치하면 많은 비용이 드는 것은 자명합니다. 그렇다면 C명 이상이기는 하지만, 이득을 볼 수 있는 최대 구간이 어디까지인지 확인하고 최솟값을 찾으면 답을 찾을 수 있습니다.

 

또 다른 예시를 들어보겠습니다.

1명의 고객만 유치하면 되는데 도시는 (1 100), (100 1)으로 두 곳입니다.

그렇다면 (100 1)을 선택하여 100명을 고르는 것이 1의 비용으로 가장 최적해가 됩니다. 조금만 생각해 보면 이게 가장 극단적인 예시임을 알 수 있습니다.

 

그렇기 때문에 C + 100까지 유치할 수 있다고 생각하고, dp테이블을 C + 100의 길이로 만든 후에 C부터 C + 100까지의 값 중에 최솟값을 찾으면 진짜 최적해를 구할 수 있습니다.

 

내용에 비해 설명을 어렵게 한 감이 있습니다. 이해가 안 된다면 소스 코드를 참고 바랍니다.

그럼에도 이해가 안 된다면 댓글로 남겨주시면 답변해드리겠습니다.

 

---

[소스 코드] / C++

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

class Ad {
public:
    int c, w;

    Ad() { }

    Ad(int c, int w) {
        this->c = c;
        this->w = w;
    }
};

int knapsack(vector<Ad> ads, int C, int N) {
    const int INF = 1000000;

    vector<int> dist(1100, INF);
    dist[0] = 0;

    for (Ad ad : ads) {
        for (int j = 1; j < 1100; j++) {
            if (j - ad.w > -1) {
                dist[j] = min(dist[j], dist[j - ad.w] + ad.c);
            }
        }
    }

    int ans = dist[C];

    for (int i = C + 1; i < 1100; i++) {
        ans = min(ans, dist[i]);
    }

    return ans;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int C, N; cin >> C >> N;
    vector<Ad> ads(N, Ad());

    for (int i = 0; i < N; i++) {
        int c, w; cin >> c >> w;
        ads[i] = Ad(c, w);
    }

    cout << knapsack(ads, C, N);
   
    return 0;
}