[백준 1106] 호텔

▪︎ 문제

---

백준 1106 문제

▪︎ 알고리즘 설계

---

• 예시
  • 목표 고객 수 C = 10
  • 도시 A: 고객 3명 확보, 비용 2
  • 도시 B: 고객 5명 확보, 비용 4
  • 초기값: dp[0] = 0, dp[나머지] = INF (매우 큰 값)
  • dp 배열은 확보할 수 있는 고객 수를 인덱스로 하여 그에 대한 최소 비용을 배열로 나타냄
• DP 흐름:
  1. i=1,2: 어떤 도시도 사용 불가, 도시 A(3명)와 B(5명) 둘 다 고객 수가 i보다 큼
  2. i=3:
     • 도시 A: dp[3] = 2
     • 도시 B: i - 5 < 0 → 사용 불가
  3. i=4: 갱신 불가
     • 도시 A: i - 3 = 1 → dp[1] + 2 = INF + 2
     • 도시 B: i - 5 < 0 → 사용 불가
  4. i=5:
     • 도시 A: i - 3 = 2 → dp[2] + 2 = INF + 2
     • 도시 B: dp[5] = 4
  5. i=6:
     • 도시 A: i - 3 = 3 → dp[3] + 2 = 2 + 2 = dp[6] = 4
     • 도시 B: i - 5 = 1 → dp[1] + 4 = INF + 4
  6. i=7:
     • 도시 A: i - 3 - 3 = 1 → dp[1] + 4 = INF + 4
     • 도시 B: i - 5 = 2 → dp[2] + 4 = INF + 4
  7. i=8:
     • 도시 A: i - 3 = 5 → dp[5] + 2 = 6 = dp[8] = 6
     • 도시 B: i - 5 = 3 → dp[3] + 4 = 6 = dp[8] = 6
  8. i=9:
     • 도시 A: i - 3 - 3 - 3 = 0 → dp[9] = 6
     • 도시 B: i - 5 = 4 → dp[4] + 4 = INF + 4
  9. i=10:
     • 도시 A: i - 3 = 7 → dp[7] + 2 = INF + 2
     • 도시 B: i - 5 = 5 → dp[5] + 4 = dp[10] = 8
• 따라서, 고객을 모을 수 있는 최소 비용은 8이 된다.
  • 경우1: dp[10] = 8 → 10명, 비용 8
  • 경우2: dp[3] + dp[5] + dp[3] = 8 → 11명, 비용 8

▪︎ 코드

---

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

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[] cost = new int[N]; // 홍보 비용
        int[] customer = new int[N]; // 홍보 후 고객 증가 수

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

        // dp[i] = i명의 고객을 확보하기 위한 최소 비용
        int INF = 100000; // 초기값은 매우 큰 값(INF)으로 설정 (최소값을 찾기 위해)
        int[] dp = new int[C + 101]; // C 이상을 고려하기 위해 C+100까지 공간 확보
        Arrays.fill(dp, INF); // dp 배열 INF로 초기화
        dp[0] = 0; // 0명의 고객을 확보하는 데 필요한 비용은 0원

        for (int i = 1; i < dp.length; i++) { // 확보 고객 수 i
            for (int j = 0; j < N; j++) { // 홍보할 도시 j
                if (i - customer[j] >= 0) { // 현재 고객 수 i에서 홍보 후 고객 수를 뺀 값이 0 이상일 때만 갱신 가능
                     // 기존 dp[i] vs (i - customer[j])명의 고객을 확보 후 도시 j를 한 번 더 사용하는 경우
                    dp[i] = Math.min(dp[i], dp[i - customer[j]] + cost[j]);
                }
            }
        }

        // C명 이상 확보한 경우 중 최소 비용 찾기
        int result = INF;
        for (int i = C; i < dp.length; i++) { // C 이상 고객 확보 가능한 모든 경우 중
            result = Math.min(result, dp[i]); // 최소 비용을 선택
        }

        System.out.println(result);
    }
}

• 도시 j를 마지막으로 사용한다고 가정하면, (모든 경우를 고려하기 위해 반복문 돌면서 가정)
  • 그 전에 (i - customer[j])명 확보하는 데 비용이 dp[i - customer[j]] (즉, 도시 j를 사용하기 전에 이미 확보한 고객 수 상태)
  • 거기에 도시 j를 한 번 더 쓰면 비용은 + cost[j]
• 기존 값(dp[i])과 비교해서 더 작은 값을 저장한다

▪︎ 시간복잡도

---

O(N × C)

▪︎ 틀린 이유

---

• HashMap으로 도시 정보를 저장함 → 도시를 한 번만 사용 가능하다고 가정
  • 문제에서는 같은 도시를 여러 번 홍보 가능(무한 배낭 문제)
  • HashMap은 같은 key(고객 수)를 덮어쓰기 때문에 중복 홍보 고려 불가
• DP(동적 계획법) 로직을 생각하지 못함
  • 문제는 최소 비용을 구해야 하는데
  • 단순 반복이나 while문으로는 모든 경우를 탐색하기 어렵다.
  • dp[i] 배열을 사용해 최소 비용을 점진적으로 갱신해야 한다.
• C명 이상 확보하는 경우를 고려하지 않음
  • 목표는 적어도 C명이므로 정확히 C명이 아니라, C보다 큰 고객 수도 계산해야 한다.
• 도시 고객 수가 i보다 클 때 처리 로직 부재
  • i - customer[j]가 음수가 되면 이전 상태가 없으므로 갱신 불가
  • 이 경우는 DP에서 안전하게 제외해야 한다.

▪︎ 느낀점 / 기억할 정보

---

• dp란?
  • 큰 문제를 작은 문제로 나누어 해결하고, 그 결과를 재사용하는 방법
  • 배열(dp[])에 부분 문제의 결과를 저장해 두고, 나중에 다시 계산하지 않고 꺼내 씀
• dp[i] = 고객 i명을 확보하기 위한 최소 비용

• 무한 배낭 문제

    for (int i = 1; i < dp.length; i++) {
        for (int j = 0; j < N; j++) { // 도시 j는 무제한 사용 가능
            if (i - customer[j] >= 0) {
                dp[i] = Math.min(dp[i], dp[i - customer[j]] + cost[j]);
            }
        }
    }