[BOJ/DP] 백준 1106 - 호텔 (Java)

1106 - 호텔

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

문제

홍보할 수 있는 도시가 주어지고 각 도시별로 홍보하는데 드는 비용
/ 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보
ex. 어떤 도시에서 9원 들여서 홍보 -> 3명 고객 늘어남 => 돈에 정수배만큼 투자할 수 있음
9원 -> 3명, 18원 -> 6명, 27원 -> 9명 (O) / 3원 -> 1명, 12원 -> 4명 (X)
=> 호텔 고객 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값

입력
첫째 줄: C (<= 1,000, 자연수), 홍보할 수 있는 도시 개수 N (<= 20, 자연수)
둘째 줄 ~ N개 줄: 도시에서 홍보할 때 대는 비용, 그 비용으로 얻을 수 있는 고객 수 (<= 100, 자연수)
출력: 문제의 정답

---

풀이

배낭 문제(Knapsack Problem)

제한된 무게/비용 안에서 가치/이익을 최대화해서 조합 찾는 문제

• 0-1 배낭(0-1 Knapsack): 아이템 한 번만 가능
  • ex. 각 물건 한 번만 담을 수 있음
  • 가치 최대화: `dp[j] = max(dp[j], dp[j - wegith] + cost)`
  • for문 역방향 (중복 방지): `capacity -> weight`

• 무한 배낭(Unbounded Knapsack): 아이템 여러 번 가능
  • ex. 같은 물건 여러 번 담을 수 있음
  • `dp[j] = min(dp[j], dp[j - wegith] + cost)`
    • `dp[j]`: j만큼의 용량/고객 수 채우는 최소 비용 / 최대 가치
    • `weight`: 아이템 무게/비용
    • `cost`: 아이템 가치/고객 수 
    • => 아이템 무한히 쓸 수 있으므로 j가 weight 이상일 때 계속 갱신
  • for문 정방향: `weight -> capacity`

• 부분 배낭(Fractional Knapsack): 아이템 쪼개서 가능
  • ex. 일부만 담을 수 있음
  • 탐욕법(Greedy) 사용 DP X
    • `가치 / 무게` 비율 큰 순서대로 담기

 

• `dp[i]`: i명 고객을 확보하기 위한 최소 비용
  • `dp[0] = 0`: 0명 확보하는 데 0원
  • `dp[1~] = INF`: 아직 확보 X

int[] dp = new int[C + 101];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;

 

무한 배낭

• `j-num`: 이미 확보된 고객 수 / `dp[j - num]`: 그 상태까지의 최소 비용
  • 현재 도시 한 번 더 써서 `num`명의 고객을 더 확보
    -> 도달 가능한 이전 상태(`j - num`)가 존재하는지 확인
  • ex. cost = 3, num 5 => 광고 1회 비용 3, 고객 5명 확보
    • j = 5 -> `dp[5] = min(dp[5], dp[5 - 5] + 3)`
      • `dp[5 - 5] = dp[0] = 0` => 5명 이전 상태(0명) 존재하니까 가능 -> dp[5] = 3
    • j = 10 -> `dp[10] = min(dp[10], dp[10 - 5] + 3)`
      • `dp[10 - 5] = dp[5] = 3` => 5명 확보한 상태(3명) 존재하니까 가능 -> dp[10] = 6
• `dp[j - num] != INF`: 이전 상태가 존재하는 경우만 계산

for (int i = 0; i < N; i++) {
    int cost = arr[i][0];
    int num = arr[i][1];

    for (int j = num; j < C + 101; j++) {
        if (dp[j - num] != Integer.MAX_VALUE) {
            dp[j] = Math.min(dp[j - num] + cost, dp[j]);
        }
    }
}

---

예시

12 2 / 3 5 / 1 1 

확보해야 하는 최소 고객 수(C): 12/ 광고 가능한 도시 개수(N): 2

• 광고 1회 드는 비용 3, 5명 고객 유치
• 광고 1회 드는 비용 1, 1명 고객 유치

=> 두 도시 적절히 조합해서 12명 이상 유치, 광고비 최소

도시1 광고 횟수	도시2 광고 횟수	총 고객	총 비용
0	12	12	12
1	7	12	3 + 7×1 = 10
2	2	12	6 + 2×1 = 8
3	0	15	9

 

---

코드

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

// 호텔
public class boj_1106 {
    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[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[C + 101];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            int cost = arr[i][0];
            int num = arr[i][1];

            for (int j = num; j < C + 101; j++) {
                if (dp[j - num] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j - num] + cost, dp[j]);
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = C; i < C + 101; i++) {
            ans = Math.min(ans, dp[i]);
        }

        System.out.println(ans);
    }
}