백준 1106 [자바] java 호텔

문제 링크: https://www.acmicpc.net/problem/1106

1106번: 호텔

 

▶문제

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

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

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

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

---

 

▶입력

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

---

▶출력

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

---

▶해설

문제에서 "적어도" 라는 말을 주목할 필요가 있습니다. 호텔의 고객을 정확하게 c명 모집하는 것이 아니라 c+1, c+2 ~~ c+100와도 상관이 없다. 즉 최소한의 비용으로 목표치를 넘어서도 상관없다는 뜻입니다. 그래서 dp [] 배열을 dp [c+1]이 아닌 dp [c+101]을 선언해줍니다. 그 이유는 한 번 홍보할 때 유치할 수 있는 고객의 수가 100을 넘지 않기 때문에 dp [c]가 목표치지만 가성비 도시가 있어서 dp [c]>dp [c+20] 이런 상황이 나올 수 있기 때문에 dp [c+101]으로 선언해줍니다. 

배열은 큰 수로 초기화 해줍니다. 

어떠한 도시가 주어졌을 때 비용과 고객 수를 cost, people로 할당해줍니다. 반복문을 이용하여 해당 도시에서 유치할 수 있는 고객 people부터 시작하여 c+101까지 모든 값을 구해줍니다. 구해진 값을 비교하여 작은 값을 선택하면 됩니다. 

for(int i=0; i<n; i++){
    String[] s1 = br.readLine().split(" ");
    int cost = Integer.parseInt(s1[0]);  
    int people = Integer.parseInt(s1[1]);
    for(int j=people; j<c+101; j++){
        dp[j]=Math.min(dp[j],cost+dp[j-people]); // people부터 시작하여 c+101까지 진행합니다.
    }
}

만약 people가 2라면

1. dp[2] = dp [2], cost+dp [2-2]가 됩니다.

2. dp[3] = dp [3], cost+dp [3-2]  -> 이때 dp [1]과 dp [3]은 같은 값이었지만 cost가 더해져 dp [1]의 값이 선택됩니다.

3. dp[4] = dp [4], cost+dp [4-2]  -> dp [2]의 값은 가장 먼저 구한 dp [2] 값이 대입되어 dp [4]의 값이 할당됩니다.

 

이처럼 모든 도시들의 비용과 고객들을 전부 비교하여 진행하면 답을 구할 수 있습니다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    static int c, n;
    static int [] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        c = Integer.parseInt(s[0]);
        n = Integer.parseInt(s[1]);

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

        for(int i=0; i<n; i++){
            String[] s1 = br.readLine().split(" ");
            int cost = Integer.parseInt(s1[0]);
            int people = Integer.parseInt(s1[1]);
            for(int j=people; j<c+101; j++){
                dp[j]=Math.min(dp[j],cost+dp[j-people]);
            }
        }
        int result=Integer.MAX_VALUE;
        for(int i=c; i<c+101; i++){
            result=Math.min(result,dp[i]);
        }
        System.out.println(result);
    }
}