[백준]JAVA - 1106번: 호텔

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

1106번: 호텔

풀이

"호텔의 고객을 적어도 C명 늘리기 위해 형택이가 투자해야하는 돈의 최솟값을 구하시오."

문제 요구사항에서 주목해야할 건 "적어도 C명"이다.

 

만약 목표치가 10명인데 11명, 12명을 모집했을 때가 더 비용이 적게 든다면 그 비용을 출력해야한다.

예제 2번을 보면 쉽게 이해할 수 있다.

 

3명 모집 -> 1원

6명 모집 -> 2원

9명 모집 -> 3원

10명 모집 -> 6원

11명 모집 -> 5원

12명 모집 -> 4원

 

문제를 이해했다면 dp 배열의 크기를 정해줘야한다.

dp 배열의 크기는 늘려야하는 고객의 수 + 한 번 홍보할 때 모집할 수 있는 최대 고객의 수로 선언해준다.

그리고 dp 배열에는 C의 최대값 (1000) * 한 번 홍보할 때 모집할 수 있는 최대 고객 수 (100) 으로 가득 채운다.

int[] dp = new int[C+101];
Arrays.fill(dp, 100000);
dp[0] = 0;

그리고 사람을 기준으로 반복문을 돌려주면서 j명을 모집했을 경우 최소 비용을 dp 배열에 입력해주면 된다. 한 번 홍보할 때 모집할 수 있는 최대 고객 수가 100명이라고 했으므로 목표 고객수에서 101을 더한 값의 범위 내에서만 진행하면 된다.

 

범위 내 dp 배열에 입력이 끝난 후에 범위 내에서 가장 작은 값을 찾아주면 문제에서 요구하는 "적어도 C명"을 모집했을 때의 최소 비용이 출력된다.

 

<최종코드>

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[] dp = new int[C+101];
        Arrays.fill(dp, 100000);
        dp[0] = 0;
		
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
			
            int cost = Integer.parseInt(st.nextToken());
            int person = Integer.parseInt(st.nextToken());
			
            for (int j=person; j<C+101; j++) {
                dp[j] = Math.min(dp[j], dp[j-person]+cost);
            }
        }
		
        int ans = Integer.MAX_VALUE;
        for (int i=C; i<C+101; i++) {
            ans = Math.min(ans, dp[i]);
        }
		
        System.out.println(ans);
    }
}