[ 백준 1106 ] 호텔 (C++) - 냅색, DP

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 냅색 문제지만, 주의해야 할 점이 한가지 있다. 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구해야 하는 것이다. 이는 C명을 늘리거나 혹은 그 이상 늘렸을 때, 최소비용이 되어야 한다는 뜻이다. 따라서 C명보다 많이 뽑아도 C명을 뽑을 때의 최소비용보다 낮다면 더 뽑아도 된다는 뜻이다.
2. 냅색 문제는 직접 보면 이해가 생각보다 쉬운 편이다. X에는 항상 최소비용이 들어가야 한다. 일단, 아무도 뽑지 않으면 0의 비용이 들어간다. 1명을 뽑을 때는 0명에서 1명을 뽑을 때 비용을 더해주면 된다. 2명을 뽑을때는 1명에서 1명을 더 뽑는 비용 vs 0명에서 2명을 뽑는 비용 중에서 낮은 비용을 넣어준다. 3명을 뽑을 때는 0명에서 3명 vs 1명에서 2명 vs 2명에서 1명을 뽑는 비용 중에서 낮은 비용을 넣어준다.
3. 0 1 2 3 4 5 6 7 8 9 10 11 // n명을 뽑을 때 0 X X X X X X X X X X X // 드는 비용
4. 위와 같이 모든 경우를 구하지만, 최대 한번에 100명을 뽑을 수 있으니 1099명까지 뽑았을 때, 최소 비용을 구해야 한다. 그런데, 코드에서는 그냥 귀찮아서 1100으로 해놨다.
5. 마지막으로 정렬하는 코드는 만약에 뽑는 인원이 처음부터 오버되면 그보다 많이 뽑는 경우는 체크하지 않기 위해서 최적화할려고 해둔 것인데, 문제풀이에는 그냥 넣지 않았다.

---

⭐️ 정답 코드 및 주석

#include<iostream>
#include<algorithm>
#include<vector>
#define INF 987654321

using namespace std;

int C, N; // 늘려야 하는 수, 도시의 갯수
int cost[1101];
vector<pair<int, int>> vec;

void input() {

    cin >> C >> N;

    for (int i = 1; i <= 1100; i++) {
        cost[i] = INF;
    }

    for (int i = 0; i < N; i++) {
        int cost, customer; cin >> cost >> customer;
        vec.push_back({ customer,cost });
    }
    sort(vec.begin(), vec.end());

}

void sol() {

    for (int i = 1; i <= 1100; i++) {
        for (auto v : vec) {
            int customer = v.first;
            int cost_ = v.second;
            if (i - customer > -1 && cost[i-customer] + cost_ < cost[i]) {
                cost[i] = cost[i - customer] + cost_;
            }
        }
    }
}

int main() {

    input();
    sol();

    int answer = INF;
    for (int i = C; i <= 1100; i++) {
        answer = min(cost[i], answer);
    }

    cout << answer;

    return 0;
}

---

🤔 문제 후기

음,,, 문제가 어렵진 않았는데, 조건중에서 C명이상이라는 말을 못봐서 계속 1000까지 구하는 것으로 해놨다가 낭패를 봤다. 문제를 좀더 꼼꼼히 읽어야겠다. 냅색 문제를 풀어보고 이해해본 사람이라면 어렵지 않은 문제라고 생각한다.