[백준] 1106번: 호텔-JAVA

문제

 

배낭문제(Knapsack) + 0/1 DP(Dynamic Programming) 문제이다.

✔️ 문제 예시 1

고객 수 목표 C가 12명이고, 2개의 도시가 있다.

• 도시 1: 3원에 5명의 고객을 유치
• 도시 2: 1원에 1명의 고객을 유치

✔️  DP 배열 초기화 및 정의

• dp의 길이는 C+100까지있다.
  • 딱 C일때의 값이 아닌 C를 넘기만 하면 되기 때문 (비용의 최댓값이 100이므로 C+100)
• dp[i]는 정확히 i명의 고객을 유치하는 데 필요한 최소 비용을 나타낸다
• dp[0]은 0으로 초기화되고, 나머지는 (C+100)*100으로 초기화를 한다.
  • -> 각 비용의 최댓값이 100이기 때문이다.

❗️주의해야 할 점

최솟값을 구할 때 적어도 C를 넘어야 하는 거지 딱 C일때의 최솟값을 구하는 건 아니므로  C~C+100의 범위안에서의 최솟값을 구해야 된다.

 

도시 별로 DP 테이블 업데이트

초기 상태 (모든 값은 매우 크게 설정)

무한대는 초기화한 값

고객	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
비용	0	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

 

도시 1 적용 후 (3원에 5명) cost: 3, people: 5

고객	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
비용	0	∞	∞	∞	∞	3	∞	∞	∞	∞	6	∞	∞	∞	∞	9

 

도시 2 적용 후 (1원에 1명) cost: 1, people: 1

고객	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
비용	0	1	2	3	4	3	4	5	6	7	6	7	8	9	10	9

 

따라서  dp[idx]=Math.min(dp[idx],cost+dp[idx-people])

 

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

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int C=sc.nextInt();
        int N=sc.nextInt();
        int[] dp=new int[C+101];
        Arrays.fill(dp, (C+100)*100);
        dp[0]=0;
        for(int i=0;i<N;i++){
            int cost=sc.nextInt();
            int people=sc.nextInt();
            for(int j=people;j<C+101;j++){
                dp[j]=Math.min(dp[j],cost+dp[j-people]);
            }
        }
        int min=Integer.MAX_VALUE;
        for(int i=C;i<=C+100;i++){
            min=Math.min(min, dp[i]);
        }
        System.out.println(min);
    }
}