[알고리즘]백준 1106_호텔

백준 1106_호텔

• dp로 각 인원 별 비용을 최소비용으로 갱신하며 진행
• 비용순으로 정렬하고 갱신하려 했으나 하다보니 의미없음을 깨달음
• 그냥 받은 비용별 고객수를 다 돌리는 방법. C명이상일 때 최소비용이니까 +99명(광고별 인원의 최대값 - 1) 까지 체크
  • c명일 때 최소비용일수도 있지만 c-1명일 때 100명을 get한 비용을 더한 게 최소일수도 있음

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[] cost = new int[N];
        int[] customer = new int[N];

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

        int limit = C + 99;

        int[] dp = new int[limit + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        // 모든 고객 수 i에 대해
        for (int i = 0; i <= limit; i++) {
   			// 최소값 갱신 안된 애들 패스
            if (dp[i] == Integer.MAX_VALUE) continue;

            // 모든 광고를 다 확인
            for (int j = 0; j < N; j++) {
                int next = i + customer[j]; // 지금 인원수 + 비용내면 get하는 인원수
                // 한도 초과 시 패스
                if (next > limit) continue;
				// 비용 최소로 갱신
                dp[next] = Math.min(dp[next], dp[i] + cost[j]);
            }
        }

        int answer = Integer.MAX_VALUE;

        // C명 이상 중 최소 비용 찾기
        for (int i = C; i <= limit; i++) {
            answer = Math.min(answer, dp[i]);
        }

        System.out.println(answer);
    }
}