[백준] 1106번 - 호텔(Java)

DP문제가 아직도 너무 어려워서, 여러 문제를 풀어보며 실력을 키우려고한다.

 

<문제>

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

 

 

 

<풀이>

아직도 점화식을 세우는 게 너무 어렵다.

이 문제도 막 어려운 편은 아닌 것 같은데, 풀지 못해서 인터넷을 참고하였다.

이런식으로 감을 익히고 많은 문제를 풀다보면, 스스로 잘 풀어낼 수 있지 않을까?

 

이 문제에서 점화식을 세우지 못하기도 했지만,

문제 조건을 간과한 점도 있다. 약간의 함정(?)이라 할 수 있는데..

"호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 것" 이라는 조건이 있다.

 

여기서 "적어도" 라는 말을 잘 캐치해야한다.
꼭 C명을 딱 맞추는 것이 아니라, 그 이상이어도 더 최솟값이라면 그것을 선택해야한다는 것이다.

그래서 점화식을 세우고 계산할 때, C + 100명까지 계산해야한다. (C + 100인 이유는 도시에서 얻을 수 있는 고객의 수가 100명이 최대)

 

dp[i] 배열은 i명을 추가하기 위한 최솟값이라고 하자.

(dp 배열을 선언할 때도, dp = new int[C + 101] 로 선언해야한다.)

dp 배열은 0 인덱스를 제외한 모든 인덱스 값을 최대값으로 선언해준다.

 

그렇게 되면, 점화식은 다음과 같다.

각 도시를 돌며, 현재 도시에서 얻을 수 있는 고객의 수 ~ C + 101까지 구해준다.

for(int i=customerCnt; i<C+101; i++) {
	dp[i] = Math.min(dp[i], cost + dp[i - customerCnt]);
}

 

그냥 dp[i]를 선택하면, 현재 도시를 선택하지 않는 것이고

cost + dp[i - customerCnt]를 선택하게 되면, 현재 도시를 선택하는 것이 된다.

 

 

<코드>

import java.io.*;
import java.util.*;

class Main {
	static int C, N;
	static int[][] promotionInfo;
	static int[] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();

		C = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		promotionInfo = new int[N][2];
		dp = new int[C+101];

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

		for (int i = 1; i <= C+100; i++) {
			dp[i] = 123456789;
		}

		for (int i = 0; i < N; i++) {
			int cost = promotionInfo[i][0];
			int customerCnt = promotionInfo[i][1];
			for (int j = customerCnt; j < C + 101; j++) {
				dp[j] = Math.min(dp[j], cost + dp[j - customerCnt]);
			}
		}

		int result = Integer.MAX_VALUE;
		for (int i = C; i < C + 101; i++) {
			result = Math.min(result, dp[i]);
		}

		br.close();
		System.out.print(result);
	}

}