[knapsack][백준 1106 Gold4] 호텔 (java)

 

문제

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

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

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

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

입력

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

출력

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

 

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

 

 

---

 

접근

1. Brute Force

모든 기업(N)에 대해 투자 안하거나, 투자 한다면 최소 비용부터 최대 비용(1000)가지 투자해보는 방법을 생각할 수 있다. 

그러면 (1000)^N 조합으로 비용을 계산하여 원하는 인원보다 큰 경우 중 최소 비용을 찾아야 한다. 

당연히 시간초과! 

 

2. 규칙이 있을까

Ex 같은 비용 대비 인원 증가하는 값이 큰 기업에 우선 투자하면? 

최소 20명을 늘리려한다고 가정했을 때, 5비용에 1000명, 3비용에 20명 늘리는 2가지 방법이 있다면 전자를 선택하게 되어 틀리게 된다. 

 

3. 모든 조합 고려 -> DP의 Knapsack! 

dp정의: dp[i][p]

• i 번째 도시까지 고려했을 때, 비용 p 를 사용하여 얻을 수 있는 최대 고객 수 

점화식

• 한 도시를 여러 번 사용할 수 있게 하는 부분은 무제한(완전) 배낭 문제의 전형적인 형태
• (즉, dp[i][...]를 업데이트할 때, 이미 갱신된 같은 행 dp[i][p - costs[i]]를 참조합니다.)
• dp[i][p] = Math.max(dp[i][p], dp[i][p - costs[i]] + customer[i])

 

도시 A, B 에 대한 예제

• A에 3투자 시 5명 증가, B에 1투자 시 1명 증가
• 최소 비용으로 12명 증가시킬 수 있는 비용은 8원임을 알 수 있다. 

 

 

코드 

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

/**
 * 호텔
 * 골드4
 * https://www.acmicpc.net/problem/1106
 */
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());   // 목표 고객 C명,    1 ~ 1000
        int N = Integer.parseInt(st.nextToken());   // 도시 수 N,       1 ~ 20

        int[] costs = new int[N + 1];
        int[] customer = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            costs[i] = Integer.parseInt(st.nextToken());
            customer[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[21][100001];

        for (int i = 1; i <= N; i++) { // 도시
            for (int p = 1; p <= 100000; p++) { // 비용
                // i 번째 도시에 투자를 안하는 경우
                dp[i][p] = dp[i - 1][p];

                // i 번째 도시에 한 번더 투자한 경우, 최종적으로 여러번 투자 시 최대 값 
                if (p - costs[i] >= 0) {
                    dp[i][p] = Math.max(dp[i][p], dp[i][p - costs[i]] + customer[i]);
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int c = 1; c <= 100000; c++) {
            if(dp[N][c] >= C){
                ans = Math.min(ans, c);
                break;
            }
        }

        System.out.println(ans);
    }
}