BOJ 1106 : 호텔 [C++]

 

1106번: 호텔

 

 

어렵사리 냅색과 DP라는 생각을 떠올렸는데도 해결을 못 했었다;;

계속해서 DP를 시도하다가 재귀로 시도하여 통과했다.

 

재귀 부분 설명

배열의 인덱스는 유치한 고객 수이며 값은 비용이다.

 

하나의 도시를 0개부터 최대한으로 선택하는 경우까지 모두 비교.

최대한으로 선택하는 경우는 해당 도시 고객만으로 유치해야 할 고객을 넘어서는 시점으로 설정.

1. 해당 도시에 N배를 투자했는데도 유치해야할 고객 수와 같거나 그에 미치지 못한다면
   1. (현재까지의 비용 + 해당 도시의 비용 * N) 이 배열의 (현재 고객 수 + 해당 도시의 고객 * N) 번째의 비용보다 작다면
   2. 배열을 업데이트하고 다음 도시를 선택하도록 재귀
2. 해당 도시에 N배 투자했을 때 유치해야할 고객 수 보다 고객이 많아진 경우
   1. (현재까지의 비용 + 해당 도시의 비용 * N)의 비용이 c명을 유치했을 때 드는 비용보다 작다면
      1. 배열을 업데이트
   2. 해당 도시에 더 투자하는 경우는 고려 X 
      (해당 도시에 N배 투자했을 때 유치해야할 고객 수를 넘겼기 때문에 (N + 1) 배 투자하는 경우는 고려할 필요 X)

 

코드

#include <iostream>

int c = 0;
int n = 0;
int info[21][2];
long long dp[1001];

void sol(int customer, int cost, int index) {
    for (int i = index; i < n; i++) {
        for (int j = 0; j < c / info[i][1] + 2; j++) {
            if (customer + info[i][1] * j <= c){
                if (cost + info[i][0] * j < dp[customer + info[i][1] * j]) {
                    dp[customer + info[i][1] * j] = cost + info[i][0] * j;
                    sol(customer + info[i][1] * j, cost + info[i][0] * j, index + 1);
                }
            } else {
                if (cost + info[i][0] * j < dp[c]) {
                    dp[c] = cost + info[i][0] * j;
                }
                break;
            }
        }

    }
}

int main()
{
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    std::ios::sync_with_stdio(false);

    std::cin >> c >> n;

    for (int i = 0; i < n; i++) {
        int cost = 0, customer = 0;
        std::cin >> cost >> customer;
        info[i][0] = cost;
        info[i][1] = customer;
    }
    for (int i = 0; i < 1001; i++) {
        dp[i] = 200000000;
    }

    sol(0, 0, 0);

    std::cout << dp[c] << "\n";

    return 0;
}