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

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

 

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

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

---

1.  아이디어

 

무한 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.
고객을 무게, 돈을 가치로 생각하면 되며 C명 이상을 담았을 때 최솟값을 구해야 하는 점에 주의해야한다.

---

2. 문제풀이

 

1차원 dp, 2차원 dp 두 가지 방식으로 풀어봤고 최솟값을 저장하는 배낭 문제여서 최댓값으로 초기화한 후 최솟값을 저장하도록 했다.
C명 이상인 최솟값을 구해야하는 조건에서 정확히 C명일 때를 구하는게 아님에 주의해야하고 돈을 정수배만큼 투자할 수 있다는 점에서 무한 배낭 문제임에 주의해야한다.
이를 위해 dp의 크기를 C보다 크게 설정해야하는데 한번 배낭에 담을 때 고객이 최대 100명이므로 100만큼 더 크게 설정했고 중복으로 담을 수 있어서 현재 상태와 비교하도록 dp 로직을 구현했다.

---

3. 코드

 

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

public class Main_1D {

    private static class Item {
        int cost;
        int cnt;

        public Item(int cost, int cnt) {
            this.cost = cost;
            this.cnt = cnt;
        }
    }

    private static final int MAX = 100_000;

    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());

        Item[] items = new Item[1 + N];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());
            items[i] = new Item(cost, cnt);
        }

        int[] dp = new int[1 + C + 100];
        Arrays.fill(dp, MAX);
        dp[0] = 0;

        int min = MAX;

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

        for (int i = C; i <= C + 100; i++) {
            min = Math.min(min, dp[i]);
        }
        System.out.println(min);
    }
}

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

public class Main_2D {

    private static class Item {
        int cost;
        int cnt;

        public Item(int cost, int cnt) {
            this.cost = cost;
            this.cnt = cnt;
        }
    }

    private static final int MAX = 100_000;

    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());

        Item[] items = new Item[1 + N];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());
            items[i] = new Item(cost, cnt);
        }

        int[][] dp = new int[1 + N][1 + C + 100];
        Arrays.fill(dp[0], MAX);
        int min = MAX;

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

        for (int i = C; i <= C + 100; i++) {
            min = Math.min(min, dp[N][i]);
        }
        System.out.println(min);
    }
}

---

4. 후기

 

- 1차원 dp

- 2차원 dp