[백준] 1106: 호텔 - JAVA

31 May 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

dp문제.

고객수를 C명 늘려야 한다.

한 도시에서 한번의 비용으로 얻을 수 있는 고객의 수는 100이하이므로

C + 101 까지 dp배열을 만든다.

한 비용으로 얻을 수 있는 고객의 수를 value라고 할 때,

“dp[j - value] + 비용”과 “dp[j]”의 최솟값을 dp[j]에 담는다.

dp배열을 다 채운 후 인덱스가 C이상인 값들 중에서 최솟값을 찾는다.

---

메모리: 14224KB

시간: 128ms

언어: Java 11

코드

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[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        // 한 번에 얻을 수 있는 고객의 수는 100보다 작거나 같다
        // C명 이상이면 되므로 C + 101 까지 배열에 담는다
        int[] dp = new int[C + 101];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            int cost = arr[i][0];
            int value = arr[i][1];
            for (int j = value; j < C + 101; j++) {
                if (dp[j - value] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j - value] + cost, dp[j]);
                }
            }
        }

        // C명 이상 중에 최솟값 탐색
        int ans = Integer.MAX_VALUE;
        for (int i = C; i < C + 101; i++) {
            ans = Math.min(ans, dp[i]);
        }

        System.out.println(ans);

    }

}