[백준] 1106번 - 호텔 [Java][C++]

문제 링크

---

1. 문제 풀이

일종의 무한 배낭 문제로 $C$ 명 이상 확보할 수 있는 최소 비용을 찾아야 하는 문제다. 배낭을 고객으로 가치를 비용으로 설정한 배낭에서 배낭 크기가 $C$ 이상인 상황 중 배낭 가치가 최소일 때를 찾으면 된다. 이때 정확히 $C$ 명을 찾았을 때 비용이 최소가 아니라 $C$명 보다 큰 어느 순간 비용이 최소일 수 있다는 점에 주의해야 한다.

최소 비용을 갱신하며 다이나믹 프로그래밍을 해야하므로 초기엔 최댓값으로 초기화한 후 갱신을 해나가면 된다. 고객 한명의 최대 비용이 $100$ 이므로 최대 $1,000$ 명 이상 확보하는 비용이 $100,000$ 을 넘을 수 없다. dp 테이블을 전부 갱신했다면 $C$ 명 부터 $C + 100$ 명까지 중 최소 비용을 찾아서 출력하면 된다.

---

2. 코드

1. Bottom-Up 2차원 dp [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = 100_001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] costs = new int[1 + N];
        int[] people = new int[1 + N];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            costs[i] = Integer.parseInt(st.nextToken());
            people[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[1 + N][1 + C + 100];
        Arrays.fill(dp[0], 1, dp[0].length, MAX);
        for (int i = 1; i <= N; i++) {
            int cost = costs[i];
            int person = people[i];

            for (int j = 1; j <= C + 100; j++) {
                if (j < person) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i][j - person] + cost, dp[i - 1][j]);
                }
            }
        }

        int min = MAX;
        for (int j = C; j <= C + 100; j++) {
            min = Math.min(min, dp[N][j]);
        }

        System.out.println(min);
    }
}

2. Bottom-Up 1차원 dp [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = 100_001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] costs = new int[N];
        int[] people = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            costs[i] = Integer.parseInt(st.nextToken());
            people[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[1 + C + 100];
        Arrays.fill(dp, 1, dp.length, MAX);
        for (int i = 0; i < N; i++) {
            int cost = costs[i];
            int person = people[i];

            for (int j = person; j <= C + 100; j++) {
                dp[j] = Math.min(dp[j - person] + cost, dp[j]);
            }
        }

        int min = MAX;
        for (int j = C; j <= C + 100; j++) {
            min = Math.min(min, dp[j]);
        }

        System.out.println(min);
    }
}

3. Bottom-Up 2차원 dp [C++]

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 100001;

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

    int c, n;
    cin >> c >> n;

    vector<pair<int, int>> a(n);
    for (auto& p : a) cin >> p.first >> p.second;

    vector<vector<int>> dp(1 + n, vector<int>(1 + c + 100));
    fill(dp[0].begin() + 1, dp[0].end(), MAX);
    for (int i = 1; i <= n; i++) {
        int cost = a[i - 1].first;
        int person = a[i - 1].second;

        for (int j = 1; j <= c + 100; j++) {
            if (j < person) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = min(dp[i][j - person] + cost, dp[i - 1][j]);
            }
        }
    }

    cout << *min_element(dp[n].begin() + c, dp[n].end());
}

4. Bottom-Up 1차원 dp [C++]

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 100001;

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

    int c, n;
    cin >> c >> n;

    vector<pair<int, int>> a(n);
    for (auto& p : a) cin >> p.first >> p.second;

    vector<int> dp(1 + c + 100);
    fill(dp.begin() + 1, dp.end(), MAX);
    for (int i = 0; i < n; i++) {
        int cost = a[i].first;
        int person = a[i].second;

        for (int j = person; j <= c + 100; j++) {
            dp[j] = min(dp[j - person] + cost, dp[j]);
        }
    }

    cout << *min_element(dp.begin() + c, dp.end());
}

---

3. 풀이 정보

1. Bottom-Up 2차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	104 ms	14324 KB	1354 B

2. Bottom-Up 1차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	104 ms	14292 KB	1192 B

3. Bottom-Up 2차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2156 KB	780 B

4. Bottom-Up 1차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2020 KB	613 B

---