백준 1106번 호텔 G5 - DP

 

우우 아아

 

 

문제를 잘 읽자

확실히 사업가는 다르다, 최솟값을 찾아야한다.

100명의 홍보를 원한다 하더라도 100명 이상의 비용이 더 저렴하다면 그 값을 출력해야했다.

간단하게 입력 받은 금액 당 홍보 인원을 통해 현재 인원 - 입력받은 인원으로 따져서
금액을 최신화 해주었다.

현재 인원에 대한 금액 최신화 ->  현재인원 - 입력 받은 인원 + 입력받은 금액 이랑 비교

 

+ 추가로 금액의 최대가 100 이므로 +101 까지만 조회해서 효율을 챙겼다.

 

import java.io.*;
import java.util.*;
 
class Main { // Boj_1106_호텔
    public static int[] dp;
    public static int N, C, answer;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 목표 사람 수
        C = Integer.parseInt(st.nextToken()); // 도시 수
        dp = new int[N+101];
        Arrays.fill(dp, Integer.MAX_VALUE); // 배열 초기화
        dp[0] = 0;
        //input
        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            int price = Integer.parseInt(st.nextToken());
            int people = Integer.parseInt(st.nextToken());
 
            for (int j = people; j < dp.length; j++) {
                if (dp[j - people] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - people] + price);
                }
            }
        }
        answer = dp[N];
        for (int i = N; i < N + 101; i++) {
            answer = Math.min(dp[i], answer);
        }
 
        System.out.println(answer);
    }
}