[백준/Java] 1106. 호텔

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

 

 

🔍 해결 과정

호텔 손님을 적어도 C명 확보하기 위해서 드는 비용을 구해야한다는 말에 주의가 필요했던 문제였습니다.

적어도 C명을 확보해야함의 의미는 C명보다 많거나 같음을 의미합니다.

 

문제에서 C의 최댓값은 1000이고, N은 20보다 작거나 같으며 비용으로 한 번에 얻을 수 있는 고객의 수의 최댓값은 100명입니다. 

이를 계산해보면 20번 동안 최대로 확보할 수 있는 고객의 수는 2000명이 됩니다.

 

v명의 고객을 확보하기 위해 드는 비용을 cost라고 정의한다면 점화식을 세우기 위한 dp의 정의를 다음과 같이 할 수가 있습니다.

dp[v] = cost (v 명의 고객을 확보하기 위해서 드는 최소 비용)

 

이를 바탕으로 점화식을 생각해야 합니다.

최대로 학보할 수 있는 고객의 수는 2000명이므로, 저는 dp의 공간을 2001(2000번 인덱스까지 포함)로 마련하였습니다.

 

먼저 0명의 고객은 드는 비용이 0이기에 dp[0] = 0 입니다. 나머지는 아직 드는 비용을 알 수가 없으므로 비용값을 INF로 초기화합니다.

 

문제에서 N명의 고객마다 드는 비용 및 고객 수의 정보가 나오므로 각각의 고객수를 기준으로 2000까지 고객 수의 배수마다 드는 비용을 계산하는 방법을 생각할 수 있습니다. 그렇게 각각 고객 수의 배수마다 드는 비용의 최솟값을 업데이트 해주면 됩니다. 따라서 점화식은 다음과 같이 세울 수가 있습니다.

dp[v] = min(dp[v], dp[v - personCount] + cost) (personCount: 유치할 수 있는 고객 수, cost: 해당 도시에서 고객 유치시 드는 비용, v >= personCount)

 

 

이 정의에 의해서 dp를 완성하고, c명 이상에서 고객을 유치할 수 있는 최소 비용을 구하면 됩니다.

 

💬 회고점

처음에는, “v명의 고객을 확보하려면 주어진 도시(광고 수단)들을 어떻게 조합해야 할까?”라는 관점으로 접근했는데, 도시마다 인구를 여러 번 사용할 수도 있고, 각 도시 인구수의 배수마다 비용을 계산해야 하는 등 경우의 수가 너무 복잡해 보였습니다.

그래서 다른 방법을 고민하던 중, 점화식을 활용하면 각 인구 수별로 비용을 차근차근 계산하고, 동시에 최소 비용도 구할 수 있다는 사실을 깨닫게 되었습니다.

 

“점화식을 사용하면 순차적으로 특정 인구 수마다 비용을 구하고, 그 중 최소값을 찾을 수 있다”는 점을 다시 한 번 실감했습니다.

---

✏️ 코드

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

public class Main {

    private static final int MAX = 2001;
    private static final int INF = (int) 1e9;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken()); // 적어도 c명을 확보해야함. c보다 많아도 됨!!
        int n = Integer.parseInt(st.nextToken()); // 홍보할 도시의 개수
        int[] d = new int[MAX]; // d[i] : i명의 고객을 유치하기 위해서 필요한 최소 비용
        Arrays.fill(d, INF);

        d[0] = 0; // 0명은 비용이 들지 않음

        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int personCount = Integer.parseInt(st.nextToken());

            for (int j = personCount; j < MAX; ++j) {
                d[j] = Math.min(d[j], d[j - personCount] + cost);
            }
        }

        int result = INF;
        for (int i = c; i < MAX; ++i) {
            result = Math.min(result, d[i]);
        }

        bw.write(result + "");
        bw.flush();
    }
}