Boj 1106 c++ 호텔

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

 

N개의 도시가 있다. 

이 도시들을 홍보하려 할때, 최소 C명의 사람들을 끌어들이는 것을 목표로 한다. 

첫번째 줄의 입력으로는 최소 사람의 수와 도시의 개수 N이 주어진다.

 

다음 N개의 줄에는 각 도시를 홍보하는데에 드는 비용과 끌어들일 수 있는 사람의 수가 주어진다.

 

이때, 입력 값을 토대로 C명의 사람을 끌어들일 수 있는 최소비용을 출력하는 것이 문제가 요구하는 것이다.

 

0< C <= 1000,  0< N <=20

비용과 효용 

W<=100, V<=100

 

 

우선 결론부터 말하자면 자력솔에 실패하였다. 정말 오랜만에 푸는 문제이기도 하고, dp문제에 대한 연습이 부족하기  때문이기도 하다.

다음은 내가 문제를 풀기 전에 했던 생각들이다.

1. 도시가 주어진다 --> 도시별로 홍보하는 비용 and 몇 명의 고객이 늘어나는가--> dp? 냅색?
2. ex) 9원을 들여서 홍보하면 3명의 고객이 늘어난다--> 정수배만큼 투자 가능.. 18원, 27원, ......
3. 도시에는 무한명의 잠재적 고객// 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램
---> 원래의 배낭 문제에서는 용량이 정해져있었는데, 이번에는 무한정으로 담을 수 있지만, 특정 값을 만족하는 최소비용을 구하는 문제이므로 미묘하게 다르다.

4. 첫째 줄: 최소 증가 고객 C, 홍보할 수 있는 도시의 개수 N

(C<=1000, N<=20)

해석: 도시의 개수 : 각 물건의 개수 
       홍보 비용: 물건의 무게 - W
       늘어나는 고객의 수: 물건의 가치 - V


요구하는 값 : 
고객을 적어도 C만큼 늘리기 위해서 들이는 홍보비용의 합의 최솟값

이전에 풀었던 냅색문제들은 모두 가방의 용량이 주어졌을 때 그 용량을 충족하는 물건들을 담았을 때 가치의 합의 최댓값을 구하는 문제였다.

하지만 이 문제는 가치의 총합이 정해져있을 때 용량의 최솟값을 구하는 문제이다.
--> 그렇다면? 

고려 요소: 홍보를 하는데 드는 비용, 홍보를 함으로써 얻는 효용(늘어나는 손님의 수), 총 비용의 최솟값

최소한의 비용으로 C를 만족하는 도시홍보의 조합을 찾아야 한다.

여기서 동적 계획법이라는 알고리즘의 본질을 고려해볼 필요가 있다.

동적계획법은 특정 범위의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘이다.
즉, 하나의 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다. 키워드는 재활용.

그렇다면 이 문제에서 재활용되는 값은 무엇일까?

우선 기본적인 냅색문제의 접근에서 부터 시작해본다.

냅색 기본문제의 풀이 방식은

'i번째 물건까지 고려했을 때 용량이 K인 배낭에 담을 수 있는 가치의 총합의 최댓값을 배열에 저장한다'
그리고
'배열에 저장된 값을 이후에 다른 용량의 배열에 들어가는 물건들을 선정할 때 함께 고려한다' ex) 특정 물건을 배낭에 넣을 수 있을 때: 해당 물건을 넣었을 때(v[i]+dp[i-1][j-w[i]]) 와 넣지 않았을 때(dp[i-1][j] ==이전 상태 그대로) 중에서 더욱 가치가 큰 값을 dp[i][j]에 저장한다.

그렇다면 해당 문제에서 dp배열을 선언한다면 어떤 값을 저장해야 할까?

i번째 도시까지 고려하였을 때 가치의 합이 k이상인 물건들을 담기 위한 비용의 최솟값을 배열에 저장하면 되지 않을까???

C = 12

w = 3, v = 5

(12/5)*3 = 6
12 mod 5 = 2
6 + 3 = 9

C = 10

w[1] = 3, v[1] = 1
w[2] = 2, v[2] = 2
w[3] = 1, v[3] = 3

100 6

4 9
9 11 
3 4
8 7
1 2
9 8

12*4, 10*9, 25*3, 15*8, 50*1, 13*9

9*11(4*11) + 2*1(1*1) = 45

i번째 도시를 보았을 때 두가지 선택지가 있다. 
1. 해당 상품을 한번이라도 사용하여 비용을 절약할 것인지
2. 해당 상품을 아예 구입하지 않는 경우가 더 유리한지

그러면 비용이 절약되는 경우를 생각해보자.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------우선 여기까지 생각하고 구현한 코드는 제대로 작동하지 않았을 뿐더러 기본 논리마저 틀리고 말았다.

원인은 dp배열의 목적을 혼동한 것이였으리라.

 

이에 대한 해결책은 dp 배열의 목적성을 확실시 하는 것.

두가지의 풀이법이 존재한다. 특이사항은 모두 일차원 dp로 해결이 가능하다는 것.(용량 고려할 필요X)

 

 

1. dp 배열의 인덱스를 확보하고자 하는 사람의 수로 정의한다. 그리고 배열의 값을 그만큼의 사람을 확보하기 위한 최소 비용으로 정의한다.

정리하면  dp[i] = i명의 사람을 확보하기 위한 최소비용

2. dp 배열의 인덱스를 사용할 수 있는 비용으로 정의한다. 그리고 배열의 값을 그만큼의 비용으로 확보할 수 있는 사람의 최댓값으로 정의한다.

정리하면 dp[i] = i만큼의 비용으로 확보할 수 있는 고객의 최댓값

 

1번의 경우부터 이해해보자.

기본원리는 항상 dp[1] ~ dp[Max] 까지의 값을 for문을 기준으로 갱신해가며 하나씩 값을 찾아나가는 것이다.

그렇다면 Max값은 어떻게 정할까?

경계의 상황을 생각해보자. C는 최대 1000이다. 그런데 999명의 사람을 모았다고 해보자. 이때, 1명이 모자라므로 추가로 홍보를 해야만 한다. 이때 효용이 100명인 상품 밖에 존재하지 않는다면 사람을 최대 1099명까지 고려하는 상황까지 고려해야 하는 것이다. 이를 반영하여 C + Max(v) = 1100 까지 고려해보자.

dp[1] ~ dp[1100]의 값을 찾는 방법은?

 

우선 찾고자 하는 값은 비용의 최솟값이다. 어떤 상황에서든 min()을 사용해야 하므로 초기값을 모두 inf의 값으로 초기화 해주는 것을 잊지 말자. 계산을 위해 dp[0] = 0으로 초기화하는 것도 잊지 말자!!

 

그 후에는 무엇을 해야 할까?

dp배열을 초기화했으니 이제 값들을 하나씩 채워나가야 한다. 

여기서 부터는 점화식의 기본 원리만 이해하면 매우 수월하게 진행된다.

    for (int i = 0; i < N; i++) { //바깥 for문:  도시를 하나씩 방문해가는 과정
        for (int j = customer[i]; j <= C + 100; j++) {  // 1 ~ N번째 도시까지 고려함
            dp[j] = min(dp[j], dp[j - customer[i]] + cost[i]);
        }
    }

우선은 하나의 도시씩 차례대로 살펴보며 dp배열의 값을 갱신해주는 bottom_up 코드의 원리를 이해해보자.

 

가장 바깥쪽의 for문은 첫번째 도시부터 n번째 도시까지 차례대로 순회하는 것을 의미한다.

안쪽의 for 문은 i번째 도시의 효용(늘어나는 고객의 수) 부터 모집된 사람의 수의 최댓값(C+100)까지 순회한다.

 

위의 코드를 보면 다음과 같은 의문이 생길 수 있다.

' j의 초기값을 customer[i]로 정해둔 상태에서 예외처리를 해주지 않는다면 확보하고자 하는 사람보다 효용이 더 큰 경우 j < customer[i]인 경우가 반영이 안되지 않을까??(효용이 목표를 초과하는 경우)'

 

하지만 우리가 dp[C+100]까지 고려하는 이유를 이해하면 의문이 해소된다.

j < customer인 경우는 사실 고려할 필요가 없다. 정답이 나올 수 있는 범위는 dp[C] ~ dp[C+100] 사이이다. 이때문에 각각의 값을 모두 구해주는 것이다. 그러기 위해서는 dp의 인덱스, 즉 목표 사람의 수를 정확히 만족하는 값들을 찾아야 한다는 것이다.

 

고로 해당 bottom - up 코드는 도시를 하나씩 순회하며 dp배열의 값을 최소 비용으로 채워주는 것이다.

 

전체코드

#include <iostream>
#define Max 99999999
using namespace std;


int dp[1100]; // dp[j] = j명의 고객을 확보하기 위한 최소 비용
int cost[25], customer[25];

int main() {
    int C, N;
    cin >> C >> N;

    for (int i = 0; i < N; i++) {
        cin >> cost[i] >> customer[i];
    }

    for (int j = 1; j <= C + 100; j++) {
            dp[j] = Max;  // 초기값 주기
    }
    dp[0] = 0;

    for (int i = 0; i < N; i++) { //바깥 for문:  도시를 하나씩 방문해가는 과정
        for (int j = customer[i]; j <= C + 100; j++) {  // 1 ~ N번째 도시까지 고려함
            dp[j] = min(dp[j], dp[j - customer[i]] + cost[i]);
        }
    }

    int ans = Max;
    for (int j = C; j <= C + 100; j++) {
        ans = min(ans, dp[j]);
    }

    cout << ans << "\n";

}

 

 

2번의 경우는 조금더 직관적이다. 하지만 시간복잡도의 면에서는 1번이 낫다.

 

두번째 방법은 dp배열의 인덱스를 비용으로 함으로써 해당 비용으로 끌어들일 수 있는 사람의 최댓값을 저장하는 것이다.

이 방법으로는 dp[C]~dp[C+100] 사이의 값 대신 하나의 정해진 인덱스로 값을 특정할 수 있다.(물론 1번의 경우도 최솟값을 구함으로써 하나로 특정되기는 한다)

 

dp[1] , dp[2] ............dp[Max] 일때 dp[i]의 값이 처음으로 C보다 크거나 같아지는 지점의 인덱스를 출력하면 된다.

이때, Max는 C = 1000 * 100(max(w)) = 100000으로 정해진다.(1000명의 사람을 끌어들이기 위해서 효용이 1명이고 비용이 100인 상품을 1000번 구입할 때)

 

이때는 다음과 같은 bottom-up 코드가 성립한다.

    for(int i = 0; i < N; i++) {
        for(int j = cost[i]; j < Max; j++) {
            dp[j] = max(dp[j], dp[j-cost[i]] + customer[i]);
        }
    }

 

1번과 같은 원리이지만 이번에는 j만큼의 비용으로 확보할 수 있는 사람이 최댓값을 저장한다.

j = cost[i] ~ Max(인덱스가 j 이상인 dp부터 고려하여 해당 상품을 구입할 수 있는 경우만 반영)

dp[j] = max(dp[j](그대로인경우), dp[j-cost[i]] + customer[i](해당 상품을 골랐을 때 사람을 더 확보할 수 있는 경우))

 

전체 코드

#include <iostream>
#define Max 100001
using namespace std;

int dp[Max]; //인덱스는 비용, 값은 최대 손님 수로 한다. C = 1000 비용이 100이라면 1000*100 == 10000
int customer[25];
int cost[25];

int main(){
    int C, N;
    cin >> C >> N;

    for(int i = 0; i < N; i++){
        cin >> cost[i] >> customer[i];
    }
    for(int i = 0; i < N; i++) {
        for(int j = cost[i]; j < Max; j++) {
            dp[j] = max(dp[j], dp[j-cost[i]] + customer[i]);
        }
    }
    for(int i = 0; i < Max; i++){
        if(C <= dp[i]){
            cout<<i;
            break;
        }
    }

}