[백준] 1106번 : 호텔 (java)

1106번: 호텔 (acmicpc.net)

1106번: 호텔

어떻게 생각하고 문제를 풀었는가?

문제에서 유의깊게 보아야 할 부분은 '적어도 C명'이었습니다.

3원을 투자하여 5명을 얻을 수 있다면 적어도 1명을 늘리기 위해 필요한 금액도 3원이며, 적어도 3명을 늘리기 위해 필요한 금액도 3원입니다.

적어도 C명 늘리기 위해 필요한 금액의 최소값은 C부터 C+100명을 늘리기 위해 필요한 금액의 최소값으로 구할 수 있습니다. (주어진 조건에서 비용으로 얻을 수 있는 고객의 수는 최대 100명)

코드

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

class Main {
    static int c, n;
    static int[] values;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        c = Integer.parseInt(st.nextToken());
        values = new int[c+101];
        Arrays.fill(values, Integer.MAX_VALUE);
        n = Integer.parseInt(st.nextToken());
        values[0] = 0;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int reward = Integer.parseInt(st.nextToken());
            for(int j=reward; j<c+101; j++){
                int prev = values[j-reward];
                if(prev!=Integer.MAX_VALUE) values[j] = Math.min(values[j], cost+prev);
            }
        }
        int result = Integer.MAX_VALUE;
        for(int i=c; i<c+101;i++){
            result = Math.min(result,values[i]);
        }
        System.out.println(result);
        br.close();
    }
}

n개의 비용과 결과에 대한 입력마다 최소 비용을 계산하여 갱신, 모든 입력이 끝난 후 C~C+100까지의 값들을 비교하여 최소 값을 반환하여 정답을 얻을 수 있습니다.

주어진 값으로 j명을 얻기 위해 필요한 비용을 계산할 수 없는 경우를 확인하기 위해 초기 값은 Integer.MAX_VALUE로 설정하였습니다. 초기 값과의 비교를 통해 주어진 입력 값으로 갱신할 수 있는 index만을 접근할 수 있습니다.