[백준] 1106 호텔 - Java

 

 

 

dp[사용한 비용] = 최대로 늘어나는 고객 수... 로 dp 배열을 채워보자.

 

dp[j] = Math.max(dp[j], dp[j - cost[i]] + effect[i]);

 

 

점화식은 위와 같다.

 

입력으로 들어오는 홍보 정보에 대해 dp 배열을 순회하면서, 효과가 더 커지는 경우 값을 갱신해준다.

 

즉, 입력으로

 

12 2
3 5
1 1

 

가 들어오면

 

dp 인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
dp 값	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
dp 값	0	1	2	5	6	7	10	11	12	15	16	17	20	21	22	25	26	27

 

이런 식으로 dp값이 갱신된다.

 

 

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

public class Main {

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        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[] cost = new int[N + 1];
        int[] effect = new int[N + 1];

        for(int i=1; i<N+1;i ++){
            st = new StringTokenizer(br.readLine());
            cost[i] = Integer.parseInt(st.nextToken());
            effect[i] = Integer.parseInt(st.nextToken());
        }

        int dp[] = new int[10_000_000];

        for(int i=1; i<N+1; i++){
            for(int j=cost[i]; j<10_000_000; j++){
                dp[j] = Math.max(dp[j], dp[j - cost[i]] + effect[i]);
            }
        }

      
        for(int i=1; i<10_000_000; i++){
            if(dp[i] >= C){
                System.out.println(i);
                break;
            }
        }


    }
}