[백준] 1106 : 호텔 - Java

백준 문제 URL

---

문제 요약

호텔에 투숙 고객을 늘리기 위해 n개의 도시에서 광고를 진행하려 한다.
각 도시의 광고에는

• 비용(cost)
• 유치 가능한 고객 수(value)
  가 주어진다.

목표는 최소 비용으로 c명 이상의 고객을 유치하는 것이다.
단, 각 도시의 광고는 여러 번(무한히) 진행 가능하다.

---

핵심 아이디어

이 문제는 전형적인 무한 배낭(Unbounded Knapsack) 문제다.

• 각 도시 광고는 여러 번 선택할 수 있으므로,
• 앞에서부터(for j = value → dp.length) 순회하며 비용을 누적 계산해야 한다.

핵심 차이점:

• 0-1 배낭: 한 번만 선택 가능 → for j = t → cost (역순)
• 무한 배낭: 여러 번 선택 가능 → for j = cost → t (정순)

---

DP 정의 & 점화식

dp 정의

• dp[j]: j명의 고객을 유치하기 위해 필요한 최소 비용

---

초기값

• dp[0] = 0
• 그 외는 INF (즉, 매우 큰 값)으로 초기화

---

점화식

각 도시 (cost, value)에 대해,
j명 유치가 가능한 모든 경우를 순회하며 최소 비용 갱신.

dp[j] = min(dp[j], dp[j - value] + cost)
단, j >= value일 때 가능.

---

최종 답

c명 이상을 달성하는 데 필요한 최소 비용을 찾는다.

즉,
min(dp[c], dp[c+1], dp[c+2], … ) 중 최소값이 답이다.

---

전체 코드 (제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    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[][] cityInfoArr = new int[n][2]; // {비용, 유치 고객수}
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            cityInfoArr[i][0] = Integer.parseInt(st.nextToken());
            cityInfoArr[i][1] = Integer.parseInt(st.nextToken());
        }

        int maxCost = 1000 * 100; // dp 배열 크기 설정
        int[] dp = new int[maxCost + 1];
        Arrays.fill(dp, maxCost);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            int cost = cityInfoArr[i][0];
            int value = cityInfoArr[i][1];

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

        int minCost = maxCost;
        for (int i = c; i < dp.length; i++) {
            minCost = Math.min(minCost, dp[i]);
        }

        System.out.println(minCost);
    }
}

---

예제 시뮬레이션

예를 들어, C = 12, N = 3이고 각 도시 정보가 다음과 같을 때:

도시	비용	고객 수
1	3	5
2	1	1
3	4	7

• 도시 1만 여러 번 이용해도 15 고객 확보 가능 (9원)
• 도시 3과 1을 혼합하면 12명 이상 확보 가능 (8원)
• 따라서 최소 비용 = 8

---

핵심 포인트 정리

• 한 도시의 광고를 여러 번 사용할 수 있으므로 무한 배낭(Unbounded Knapsack) 구조 사용.
• for j = value → dp.length 정순 순회로 중복 가능하게 갱신.
• dp[c]가 아니라, c이상인 인덱스의 최소값이 정답.
• 메모리 최적화를 위해 1차원 dp 배열만 사용.