[Gold V] 호텔 - 1106 (Java)

문제 링크

성능 요약

메모리: 14272 KB, 시간: 128 ms

분류

다이나믹 프로그래밍, 배낭 문제

문제 설명

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이 (동적 프로그래밍 바텀 업)

시간 복잡도 O(n*m) 공간 복잡도 O(n)

아이디어: dp[] 공간을 n명을 채우기 위한 최소값의 저장 공간으로 생성, 비용과 비용대비 증가하는 사람의 수를 따로 배열로 저장

dp[n] = dp[n-people] + cost 의 관계식을 정의하여 풀이

"호텔의 고객을 적어도 C명 늘이기 위해" 즉 dp[C]를 출력하라는 것이 아니라 dp[C] 이상의 구간에서 그 보다 작은 값이 있으면 출력하여야 한다. 

그래서 필자는 c의 범위가 1000 아래라는 것을 이용해 일부로 dp공간을 1000더 잡아서 혹여나 dp[c] 다음 인덱스에 더 작은 값이 있을 경우 해당 값을 출력하도록 코드를 수정하였다.

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

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    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());
        long[] dp = new long[c+1001];
        Arrays.fill(dp,Integer.MAX_VALUE);
        int[][] info = new int[n][2];
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int money = Integer.parseInt(st.nextToken());
            int people = Integer.parseInt(st.nextToken());
            info[i] = new int[]{money, people};
        }
        for (int i = 1; i <= c+1000; i++) {
            for (int j = 0; j < n; j++) {
                int money = info[j][0];
                int people = info[j][1];
                if(i-people>=0) dp[i] = Math.min(dp[i],dp[i-people]+money);
            }
        }

        long ans = dp[c];
        for (int i = c+1; i <=c+1000 ; i++) ans = Math.min(ans,dp[i]);

        System.out.println(ans);

    }
}