[Algorithm]Baekjoon 1106번 : 호텔

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

1106번: 호텔

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
 
int c, n;
int costs[21] = { 0 };
int customers[21] = { 0 };
int dp[1001] = { 0 }; // dp[i] == i명 구하는데 필요한 최소비용.
 
int advertise(int customerCount)
{
    if (customerCount <= 0) return 0; // 이미 다구함.
    if (dp[customerCount] > 0) return dp[customerCount]; // 이전에 계산했음.
 
    dp[customerCount] = 100000;
 
    for (int i = 0; i < n; ++i)
    {
        dp[customerCount] = min(dp[customerCount], advertise(customerCount - customers[i]) + costs[i]);
    }
 
    return dp[customerCount];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> c >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> costs[i] >> customers[i];
    }
 
    cout << advertise(c);
}

 

문제를 단순화해보면, 익숙한 유형의 문제이다.

최소 n명의 인원을 맞추기 위한 최소비용을 구하시오... 이다.

일단은 탑다운방식이 더 직관적이게 떠올라서 해당 풀이를 했다.

이후 바텀업방식도 내가 풀줄 알아야 이 문제를 이해했다고 말할 수 있을 것 같아서 바텀업방식으로도 풀어봤다.

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
 
int c, n;
int costs[21] = { 0 };
int customers[21] = { 0 };
int dp[100001] = { 0 }; // dp[i] = i원일때 최대 인원수.
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> c >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> costs[i] >> customers[i];
    }
 
    for (int i = 0; i < n; ++i) // 최대 20.
    {
        int cost = costs[i];
        int customer = customers[i];
 
        for (int j = cost; j <= 100000; ++j)
        {
            dp[j] = max(dp[j], dp[j - cost] + customer);
        }
    }
 
    for (int i = 1; i <= 100000; ++i)
    {
        if (dp[i] >= c)
        {
            cout << i;
            break;
        }
    }
}

 

Top-Down방식과 다르게, 여기서 dp테이블이 의미하는것은

 

dp[i] = i원일 때, 최대 인원수

 

이다.

코드가 기본적인 냅색문제랑 유사하긴 한데, 보통 기본냅색문제는 각 물건을 한가지씩만 담는식으로 문제가 되어있는 경우가 많으니, 아예 똑같이 코드를 작성하면 정답이 아니다.

왜냐하면 이 문제는 같은 물건(도시)를 여러번 담을 수 있기 때문이다.

이 점만 유의해서 풀면 된다.