[백준/C++]#1106- 호텔

코드1

#include <bits/stdc++.h>

using namespace std;

int C, N;
// 비용
int cost[21];
// 고객의 수
int human[21];
// Dp의 크기
int D[1101];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> C >> N;
    int inp1, inp2;
    // 절대 나올 수 없는 값으로 초기화
    fill(D, D+1101, 10000000);
    int maxi = INT_MIN;
    for (int i=0; i<N; i++) {
        cin >> inp1 >> inp2;
        // 가장 큰 고객의 수
        maxi = max(maxi, inp2);
        cost[i] = inp1;
        human[i] = inp2;
        // 해당 고객에 대해 가장 작은 비용의 값이 저장됨
        D[human[i]] = min(D[human[i]], cost[i]);
    }
    // 적어도 C명이므로 최대 C+maxi까지 계산해야 전체 케이스가 보장됨
    for (int i=1; i<=C+maxi; i++) {
        for (int j=0; j<N; j++) {
            if (i <= human[j]) continue;
            D[i] = min(D[i], D[i-human[j]] + cost[j]);
        }
    }
    // 적어도 C명이상의 최소 비용 계산
    int mini = D[C];
    for (int i=C+1; i<=C+maxi; i++) mini = min(mini, D[i]);
    cout << mini << '\n';
    return 0;
}

풀이1

D[x] = x의 고객에 대한 최소 비용

 

1. 입력으로 제공된 해당 고객에 대해 가장 작은 비용의 값을 DP 테이블에 작성한다.
2. DP[C+maxi]까지 반복문을 돌며, min(현재 DP값, 이전 DP값에서 해당 고객 뽑았을때의 비용 합)을 DP 테이블에 넣는다. 

---

 

+a

• Dp 크기 1100
  • C의 최댓값 1000 + 고객의 수 최댓값 100 = 1100
• 최대 Dp에 나올 수 있는 최댓값 100,000 = 1000 x 100 이므로 그보다 크게 초기화
  • 초기화하는 이유는 min 연산 사용하기 위하여
• 동일 고객의 수에 대해, 가장 작은 비용의 값만 저장하면 됨
  • 100명 고용하는데 10 듦 vs 20 듦
  • 20 드는 경우는 절대 사용할 필요 없음
• C+maxi 까지 고려하는 이유
  • D[C] 의 경우 = C명에 대한 비용
  • 하지만 적어도 C명 늘리는 경우 C보다 크며, 비용이 더 작아질 수 있음
  • D[C] ~ D[C + maxi] 의 경우 = 모든 경우 보장

 

 

코드2

#include <bits/stdc++.h>

using namespace std;

int C, N;
// 비용
int cost[21];
// 고객의 수
int human[21];
// Dp 크기
int D[100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> C >> N;
    int inp1, inp2;
    int maxi = INT_MIN;
    for (int i=0; i<N; i++) {
        cin >> inp1 >> inp2;
        // 가장 큰 비용의 수
        maxi = max(inp1, maxi);
        cost[i] = inp1;
        human[i] = inp2;
        // 해당 비용에 대해 가장 큰 고객이 저장됨
        if (D[cost[i]] != 0) D[cost[i]] = max(D[cost[i]], human[i]);
        else D[cost[i]] = human[i];
    }
    // 최대 비용의 크기 = C x 가장 큰 비용
    for (int i=1; i<=C*maxi; i++) {
        for (int j=0; j<N; j++) {
            if (i <= cost[j]) continue;
            D[i] = max(D[i], D[i-cost[j]] + human[j]);
        }
    }
    // C명 이상이 되자마자 index의 크기 = 최소 비용
    for (int i=1; i<=C*maxi; i++) {
        if (D[i]>=C) {
            cout << i;
            break;
        }
    }
    return 0;
}

 

풀이2

D[x] = x의 비용에 대한 최대 크기의 고객

 

1. 입력으로 제공된 해당 비용에 대해 가장 큰 고객의 값을 DP 테이블에 작성한다.
2. DP[C*maxi]까지 반복문을 돌며, min(현재 DP값, 이전 DP값에서 해당 비용 지불했을 때의 고객 합)을 DP 테이블에 넣는다. 

 

---

 

+a

• Dp의 크기 100,000
  • = 최대 비용 = 100 (드는데 1명뽑음) x 1000 (명 뽑음)
• C*maxi 까지 고려하는 이유
  • D[C] 의 경우 = 1명 당 1 비용 들때의 이야기
  • D[C*maxi] 의 경우 = 1명 당 maxi 비용 들때의 이야기