220823 - 호텔

◾ 호텔 : 백준 1106번 (골드 5)

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

문제

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

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

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

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

---

입력

• 첫째 줄 : 목표 고객 수 C(1 <= C <= 1000 / 자연수), 도시의 개수 N(1 <= N <= 20 / 자연수)
• 이후 N줄 : 도시 홍보 비용과 얻을 수 있는 고객의 수.

출력

• 투자해야하는 최소한의 금액.

입출력 예

Input	Output
12 2 3 5 1 1	8

---

◾ 풀이

1. 해설

• 동적 프로그래밍을 통해 각 추가 고객에 따른 최소 비용 계산.
  • dp[i] : i 고객 추가를 위한 최소 비용.s
    • 홍보 비용 : cost, 홍보 추가 고객 : profit
    • dp[i] = min(dp[i-p]+cost, dp[i]) (i >= profit)
    • dp[i] = min(cost, dp[i]) (i < profit)

---

2. 프로그램

1. 목표 고객의 수, 도시의 수 입력.
2. 도시 홍보 정보 입력.
3. dp 초기화 : 최대값

• 단, 인덱스 0은 0으로 초기화.

4. 각 고객수에 대해 도시 홍보 비용을 비교하여 최소값으로 갱신.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 홍보 클래스.
class Promotion{
	int cost;	// 비용
	int profit;	// 고객 추가.
	
	public Promotion(int cost, int profit) {
		super();
		this.cost = cost;
		this.profit = profit;
	}
}

public class Main {
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		// 목표 고객, 도시의 개수 입력.
		st = new StringTokenizer(in.readLine());
		int c = Integer.parseInt(st.nextToken());	// 목표 고객
		int n = Integer.parseInt(st.nextToken());	// 도시의 개수
		
		// 홍보 정보 입력.
		Promotion[] p = new Promotion[n];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			int cost = Integer.parseInt(st.nextToken());	// 홍보 비용
			int profit = Integer.parseInt(st.nextToken());	// 추가 고객
			
			p[i] = new Promotion(cost, profit);
		}
		
		// DP : 고객의 수에 따른 홍보 비용 최소값
		// - 최대값으로 초기화
		// - 0은 0으로 초기화.
		int dp[] = new int[c+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		
		// 추가 고객의 수에 따라 최소 비용 계산.
		for(int i = 1; i <= c; i++) {
			// 모든 홍보 탐색.
			for(Promotion cur : p) {
				// 추가 고객의 수가 목표 고객보다 큰 경우.
				if (cur.profit > i) {
					dp[i] = Math.min(cur.cost, dp[i]);
				// 추가 고객의 수가 목표 고객보다 작거나 같은 경우.
				}else {
					dp[i] = Math.min(cur.cost+dp[i-cur.profit], dp[i]);
				}
			}
		}
		
		sb.append(dp[c]);
		System.out.println(sb);
	}
}