[백준] 1106번: 호텔 - java

문제

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

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

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

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

입력

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

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());
		int n = Integer.parseInt(st.nextToken());
		
		// 각 도시에서 비용으로 얻을 수 있는 고객수는 100명 이하
		// 적어도 C명을 늘여야하므로 그보다 더 큰 고객을 들였을 때의 비용이 더 작을 수 있음
		int dp[] = new int[c+100]; 
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int cost = Integer.parseInt(st.nextToken());
			int customer = Integer.parseInt(st.nextToken());
			
			for(int j=customer; j<c+100; j++) {
				// 돈에 정수배 만큼 투자할 수 있으므로
				// cost(현재 비용) + dp[j-customer] 로 j명의 고객을 늘린다.
				if (dp[j-customer] != Integer.MAX_VALUE) // 무한이라면 아직 갱신되지 않은 값이므로 고객을 확보할 수 없다
					dp[j] = Math.min(dp[j], cost+dp[j-customer]);
			}
		}
		
		int answer = Integer.MAX_VALUE;
		for(int i=c; i<c+100; i++) {// 최소 c명을 확보해야 하므로 dp[c]부터 탐색
			answer = Math.min(answer, dp[i]);
		}
		System.out.println(answer);
		
	}

}

 

 

간단해 보이지만, 생각보다 조건이 까다로웠다.

1. 정수배로 돈을 투자할 수 있다는 조건
2. C명이 아니라, 최소 C명의 고객을 늘리기 위한 최소 비용을 구해야 한다는 조건

해당 조건을 만족시키는 dp점화식을 세우면 된다.

 

 

---

먼저 dp[i] 는 i명의 고객을 늘리기 위한 최소 비용이다.

 

따라서 for문으로 dp[i] 를 갱신할 수 있다.

이때 주의해야할 점이 보통의 문제라면 for(int i=고객수; i<c; i++) 까지 탐색할텐데,

우리는 최소 C명의 고객을 확보하는 것이지, 딱 C명을 맞춰야 하는 것이 아니다. 

 

예로, dp[c] = 100 이고 dp[c-1]=1, dp[c+100]=2인 경우를 생각해보자.

즉, c명을 확보할 때는 100의 비용이 들지만, (c-1) + (c+100) => c+99명을 확보할 때는 1+2=3이 될 것이다.

따라서 c명보다 더 큰 값에서 최소비용이 들 경우를 생각하여,

각 도시가 확보할 수 있는 최대 100명의 고객을 더해 for(int i=고객수; i<c+100; i++) 으로 탐색하는 것이다.

 

---

그런다음 dp[i]값을 갱신하는데, dp[i] = Math.min( dp[i], cost+dp[i-customer] ) 으로 구할 수 있다.

현재 도시에서 3명을 유지하는데 9라는 비용이 든다고 가정하자.

dp[0] = 0 으로 초기화한다.

dp[3] = cost + dp[0] => 9

dp[4] => cost + dp[1] 인데, dp[1] 은 아직 갱신되지 않은 값이므로 cost+dp[1]은 cost+무한으로 overflow 가 발생해 음수의 무한 값을 가지게 될 것이다. 

이를 방지하기 위해 dp[i-customer] != Math.Integer 라는 조건을 추가해주었다.

계속해서 갱신한다면

dp[6] => cost+dp[3] => 18

...

dp[30] => cost + dp[27] => 90 이 될 것이다.

---

 

 

조건을 꼼꼼히 구현하도록 하자..!