[Java] 백준 1106번: 호텔

🔗 문제

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

 

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

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

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

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

 

 

💭 풀이 과정

투자금 weight, 고객 value로 최소 C를 만족하는 최소의 weight로 해석하면 배낭 문제라는 것을 알 수 있다.

게다가 정수배만큼 투자를 할 수 있다는 건 쪼갤 수 없는 배낭 문제라고 힌트를 준거나 다름이 없다.

 

dp[고객수] = 최소 투자금

 

단순한 배낭 문제와 다르게 “적어도” C명 이상일 때 투자해야 하는 돈의 최솟값을 구하는 것에 차이가 있다.

입력되는 투자금의 최대금액이 100이므로 dp를 구하는 for문의 범위를 100만큼 더 늘려 계산해 주면 된다.

 

 

🚀 전체 소스

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 answer = Integer.MAX_VALUE;
        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        List<int[]> info = new ArrayList<>();
        int[] dp = new int[C+101];
        Arrays.fill(dp, Integer.MAX_VALUE);

        for(int i=0; i<N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int profit = Integer.parseInt(st.nextToken());
            info.add(new int[]{cost, profit});
            dp[profit] = Math.min(dp[profit], cost);
        }

        for(int p=0; p<C+101; ++p)
        {
            for(int i=0; i<N; ++i)
            {
                int cost = info.get(i)[0];
                int profit = info.get(i)[1];

                if(p < profit) continue;

                if (dp[p - profit] != Integer.MAX_VALUE) {
                    dp[p] = Math.min(dp[p], dp[p - profit] + cost);
               }
            }

            if (p >= C)
                answer = Math.min(answer, dp[p]);
        }

        System.out.print(answer);

    } // main
}