BOJ 1106 - 호텔

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

그리디로 풀 수 없는 이유

그리디로 처음에 시도를 했다. 그러나 이 문제는 그리도로 절때 풀 수 없다.
원 당 모집 인원 수가 가장 많은 것을 고른다고 가정해보자.
1번 예시에서 반례가 발생한다.

``` 12 2 3 5 1 1 ``` 3원 - 2명은 원 당 1.66666667명을 모집한다. 따라서, 그리디에선 3원을 3번 선택하여 9가 정답이지만 예시의 예상 출력 값은 8이다. 따라서, 이 문제는 그리디 대신 `dp`를 이용하는 것이 옳바르다.

DP 풀이

DP[i]를 i명 모집 시의 최소 비용으로 두자. 호텔 A가 3원 당 5명이고 호텔 B가 1원 당 1명이라고 하자. DP[i]는 DP[i-3] + 5 일 수도 있고, DP[i-1] + 1 일 수도 있다. 이전 인원 단계에서 호텔 A에 모집을 했을 수도 있고, 호텔 B에 모집을 했을 수 있다. 따라서, 이는 최소값을 통해 i명 일때의 최소 비용을 구하면 되는 아주 간단한 문제이다.

---

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>

#define ll long long

using namespace std;

int c, n;
int cost[1001];
int person[1001];
int dp[1101];

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

    fill(dp, dp+1101, 1e9);

    cin >> c >> n;
    for(int i=0;i<n;i++) {
        cin >> cost[i] >> person[i];
        dp[person[i]] = min(dp[person[i]], cost[i]);
    }

    for(int i=1;i<=1100;i++) {
        for(int j=0;j<n; j++) {
            if(i > person[j]) {
                dp[i] = min(dp[i], dp[i-person[j]] + cost[j]);
            }
        }
    }

    int res = 1e9;
    for(int i=c;i<=c+100;i++) {
            res = min(res, dp[i]);
    }

    cout << res;

    return 0;
}