1106 : 호텔 Java

1106번: 호텔

0 - 1 배낭 문제로 생각하고 접근해야 하는 문제이다.

다만 배낭 문제의 경우 배낭 무게가 정해져 있어 무게를 초과한다면 넣을 수 없지만 이 문제의 경우 최소 C명 이상의 고객을 얻을 수 있는 최소 비용이기 때문에 C명을 넘더라도 최소 비용이라면 해당 값을 반환해야 한다.

풀이 과정

dp의 경우 C + 1명이 아닌 C + 101명으로 초기화 해주었는데 이는 하나의 도시에서 홍보를 통해 얻을 수 있는 고객이 최대 100명이기 때문이다.

앞서 말했듯 최소 C명이상의 고객을 얻을 수 있는 최소 비용이기 때문에 넘을 수 있는 최대 고객 수인 100명과 1번 인덱스부터 사용하기 위해 1명을 추가해줬다.

최소 비용을 구하는 문제이기 때문에 dp를 적당한 무한값으로 초기화해주고 0명을 얻기 위해서는 비용이 들지 않으니 dp[0] = 0으로 초기화해줬다.

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

현재 도시에서 j명의 고객을 얻기 위해서는 현재 도시에서 얻을 수 있는 고객을 뺀 만큼( j - people)만큼 고객을 얻는 비용에 현재 도시에서 드는 비용을 더해주면 된다.

그러나 도시들이 한정되어 있고, 얻을 수 있는 고객 수가 정해져 있기 때문에 항상 j - people만큼의 고객을 얻을 수 없다. 예를 들어 현재 도시에서 5명씩 고객을 유치할 수 있다면, 1 ~ 4명의 고객을 유치할 수 없다.

그렇기 때문에 dp[j - people]이 무한대가 아닌 값, 즉 j - people명 만큼의 고객을 얻을 수 있을 때만 j - people명의 고객을 얻는 비용 + people만큼 고객을 얻는 비용과 j 명만큼 고객을 얻는 비용을 비교해 최솟값으로 갱신하게 된다.

이제 위의 예제를 통해 dp의 값을 확인해보자.

12 2
3 5
1 1

dp = {0,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️, ...♾️,♾️,♾️,♾️}

위와 같이 113개의 원소를 가진 배열 dp가 있다.

첫 번째 도시의 cost는 3이고 people은 5이다.

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

j는 5부터 시작하므로 0(dp[0]) + 3(cost)과 ♾️를 비교해서 최솟값인 3으로 dp[5]를 갱신한다.

dp = {0,♾️,♾️,♾️,♾️,3,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️,♾️, ...♾️,♾️,♾️,♾️}

6, 7, 8, 9 까지 조건문을 충족하지 못하고 지나간다. 10이 되었을 때 비로소 dp[10 - 5] = 3이기 때문에 조건문 안쪽으로 들어간다. 무한대와 3 + 3을 비교해 최솟값인 6으로 갱신한다.

이렇게 쭉쭉 갱신하다보면 하나의 도시가 끝나고 아래와 같이 변한다.

dp = {0,♾️,♾️,♾️,♾️,3,♾️,♾️,♾️,♾️,6,♾️,♾️,♾️,♾️,9, ...♾️,66,♾️,♾️}

이제 두 번째 도시에서 확인해보자.

해당 도시에는 1의 비용으로 1명의 고객을 얻을 수 있다.

다시 한 명의 고객을 유치하기 위해서는 0명의 고객을 유치하는 비용 + 현재 도시의 비용과 1명을 얻을 때의 비용을 비교해 최솟값으로 갱신하면 된다.

따라서, 0(dp[0]) + 1(cost)와 ♾️를 비교하고 최솟값은 1을 dp[1]에 저장한다.

이후 j = 4까지 진행하면 아래와 같이 갱신된다.

dp = {0,1,2,3,4,3,♾️,♾️,♾️,♾️,6,♾️,♾️,♾️,♾️,9, ... ,♾️,66,♾️,♾️}

j = 5 일때는 이전 도시에서 5명을 홍보하는데 드는 비용인 3이 이미 기록되어 있다.

이제 dp[5] = min(dp[5 - 1] + 1, dp[5])를 비교해보면 4(dp[4]) + 1(cost)와 3(dp[5) 기존의 값인 3이 최솟값이다.

이처럼 두 비용 중 더 작은 비용을 갱신하면 된다.

그렇게 계속해서 비교하면 아래와 같이 모든 값이 갱신된다.

dp = [0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 6, 7, 8, 9, ..., 67, 66, 67, 68]

이제 dp[12]인 8부터 dp[112]인 68 중의 값 중 최솟값을 출력하면 된다.

import java.io.*;
ㄴimport java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // dp[a] = b
        // a명을 유치하기 위한 최소 비용은 b이다.
    static int[] dp;
    static int C, N;

    public static void main(String[] args) throws IOException {
//        System.setIn(Files.newInputStream(Paths.get("src/input.txt")));
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        // 홍보로 얻는 고객이 최대 100이므로 1100까지 가능
        dp = new int[C + 101];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken()), people = Integer.parseInt(st.nextToken());
            // 최소 C명이기 때문에 C명을 넘더라도 최솟값이라면 갱신
            for (int j = people; j < C + 101; j++) {
                if (dp[j - people] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j - people] + cost, dp[j]);
                }
            }

        }
        int ans = Integer.MAX_VALUE;
        for (int i = C; i < C + 101; i++) {
            ans = Math.min(dp[i],ans);
        }
        bw.write(ans+"");
        bw.flush();
        bw.close();
        br.close();
    }

}