백준 1106 호텔 java

전수민

Dec 6, 2025

TABLE OF CONTENTS

1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/1106

최소 홍보해야할 인원 수: C

N개의 도시가 존재하고 도시마다 다음이 주어짐 (고객 홍보에 드는 비용, 홍보하면 무조건 모이는 고객 수)

이때, '적어도' C명 이상 모이게 하는 최소 비용은 얼마인가?

(1) 조건 분석 📊

'적어도' 의 의미
: 모집한 인원이 C명보다 커도 된다. 즉 C 이상 모인 고객 중에 최소 비용을 구하는 문제이다.

문제를 해석하며 'DP인가?' 아니면 '그리디 알고리즘인가?' 구분이 제일 어려웠다. 필자가 내린 결론은, 순서가 있으면 그리디, 아니면 DP 라는 것이다.

선택에 순서가 있다. 즉 매 시점에 고를 수 있는 것과 없는 것이 구분되어 존재하고 일방통행으로 골라가야 한다면 그리디 알고리즘이다. 반면 선택에 순서가 없고, 똑같은 물건을 제일 먼저 선택하든, 제일 최후에 선택하든 결과에 차이를 주지 않는다면 DP에 가깝다.

가방에 물건을 최대 비용으로 담는 문제가 있을 떄, 그리디로 풀 수 있는 형태와 DP로 풀 수 있는 형태가 따로 존재한다면 다음과 같을 것이다.

그리디 알고리즘의 경우, 시간과 같은 순서를 정하는 개념이 추가로 존재할테고 매순간 선택할 수 있는 물건의 범위가 정해져 있을 것이다. 반면 DP는 순서가 없이 무조건 최대 비용을 구하라고 문제가 나왔을 것이다.

이번 백준 1106 호텔 문제 또한, 언제 어느 도시를 가든 그 순서가 상관없다. 그저 최소 비용으로 C인원 이상만 홍보하면 되는 것이다. 따라서 이번 문제는 DP에 가깝다.

2. 코드가 나오기까지 🛠️

KEY WORD: DP

(1) DP 배열 만들기

dp 배열을 만든다. dp 배열은 index = 인원 수, value = 해당 인원의 사람을 모았을 때 드는 최소 비용이다.
dp의 크기는 C+100 이어야 하는데, 이는 문제에서 밝혔던 '적어도' C 명 이상 모을 때 최소 비용을 구하라는 조건 때문에 C 이상의 사람을 구한 경우에서도 답이 되는 최소 비용이 있을 수 있기 때문이다.

왜 100을 더하냐고 한다면, 하나의 도시에서 모집할 수 있는 최대 인원이 100명이기 때문이다. 한 도시에서 정수배로 비용과 인원을 계속 더해 나간다고 쳤을 때, C ~ C +99 까지는 비용의 차이를 보일 수 있으나, C+100 부터는 특정 도시를 무조건 한 번 더 방문한다는 것이므로, 최소 비용이 나올 수 없다.

(2) 점화식

now가 현재 확인 중인 도시라고 했을 때, 수식은 다음과 같다.

$$
dp[i] = Math.max(\text{dp[i], \; dp[i-now.people] + now.cost})
$$

i 명을 수집할 때, 최소 비용은 원래 값과, (i - 현재 도시에서 구할 수 있는 인원 수)일 때의 최소비용 + 현재 도시에서 사람 구할 때 비용 중 더 최소인 비용일 구하는 것이다.
이것을 매 도시마다 반복 계산하면 된다.

(3) 시간복잡도 분석 ⏳

C+100 개의 배열을 N번 순회한다. 따라서 $O(C \times N)$ 이 최종 비용이다.

3. 코드 🌐


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

public class Main {
    static int C,N; // C = 모아야 하는 인원 수, N = 도시 수
    static int [] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        dp = new int [C + 101];
        Arrays.fill(dp, 100_001);
        dp[0] = 0;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int people = Integer.parseInt(st.nextToken());
            for(int j = people; j < dp.length; j++){
                dp[j] = Math.min(dp[j], dp[j-people]+cost);
            }
        }
        int answer = Integer.MAX_VALUE;
        for(int i = C; i < dp.length; i++){
            answer = Math.min(answer, dp[i]);
        }
        System.out.println(answer);
    }
}