[백준 1106] 호텔 - JAVA

BOJ Link

https://www.acmicpc.net/problem/1106

 

풀이 과정

문제에서 호텔의 고객을 적어도 C명 늘려야 하기 때문에, C보다 고객이 많은 경우도 고려해야 한다.

한개의 홍보로 얻을 수 있는 고객의 수는 100보다 작거나 같은 자연수이므로, C+100명까지 dp에 기록한다.

이후, C~C+100번째 dp중 최소 값(홍보비용)을 출력한다.

 

또한, 배낭 문제를 1차원 dp로 다룰 수 있다.

이때, Bounded(0-1) Knapsack인 경우 맨 뒤 인덱스부터 탐색해야 하며,

해당 문제는 Unbounded Knapsack이므로 앞의 인덱스부터 탐색한다.

 

제출 코드

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[] dp = new int[C + 1 + 100];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            for (int j = p; j <= C + 100; j++) {
                dp[j] = Math.min(dp[j], dp[j - p] + c);
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = C; i <= C + 100; i++) {
            ans = Math.min(ans, dp[i]);
        }
        System.out.println(ans);
    }
}