[Gold IV] 호텔 - 1106
성능 요약
메모리: 14380 KB, 시간: 104 ms
분류
다이나믹 프로그래밍, 배낭 문제
제출 일자
2025년 4월 28일 15:34:12
문제 설명
세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.
형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.
각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
구하고자 하는 것
적어도 C명의 고객을 얻고자 할 때, 투자해야 할 돈의 최솟값을 구해야 한다
풀이 설계하기
처음에는 i원을 쓰고 모이는 고객의 수를 구하는 식으로 점화식을 세웠다.
그러나 직관적이지 않다는 생각이 들어, i명을 모집하는 데에 드는 최소비용을 구하는 식으로 다시 해결했다.
점화식 설계하기
dp[i]는 i명을 모집하는 최소 비용을 저장하기로 하자.
임의의 케이스가 cost원을 사용해서 value명을 모집할 수 있으면,
그러면 i명을 모집하는 비용은 dp[i]로 나타내고, 이는 dp[i-value] + cost로 나타낼 수 있다.
왜냐하면 value명을 덜 모집한 비용에서 value명을 모집하는 비용을 추가하면 되기 때문이다.
물론 dp[i]와 dp[i-value] 중 최소값을 택해야 한다.
따라서 점화식은 다음과 같다
dp[i] = Math.min(dp[i], dp[i-value] + cost)
그리고 이 식의 범위는 C보다 더 멀리까지 보아야 한다.
C+1명을 모으는 비용이 C명을 모으는 비용보다 더 적을 수도 있기 때문이다.
문제의 모든 케이스에서 모집 가능한 고객의 수는 최대 100명이다.
따라서 문제의 특성상 value의 배수마다 cost의 배수가 할당되는 식인데, value가 최대 100이므로 101 이상에는 이전 value의 값들이(최소값이지만) 반복됨을 알 수 있다.
따라서 C+100 너머까지만 탐색하면 된다.
그리고 최소 범위인 C부터, 케이스별 고객 최대 수인 100을 더한 C+100까지를 탐색하여 최소값을 취하면 된다
시간 복잡도
케이스가 N개이고, 매 케이스마다 C+101까지 탐색한다.
따라서 O(NC)의 시간 복잡도를 가지고, 1000 x 20의 범위로 충분히 시간 내 해결 가능하다.
정답 코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int C = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
final int MAXIMUM_BOUND = 100001;
int[] costs = new int[N];
int[] values = new int[N];
int[] dp = new int[C + 101]; // 고객이 i명일때 최소 비용
Arrays.fill(dp, MAXIMUM_BOUND);
dp[0] = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
costs[i] = Integer.parseInt(st.nextToken());
values[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++) {
int cost = costs[i];
int value = values[i];
for (int j = value; j < C+101; j++) {
dp[j] = Math.min(dp[j], dp[j - value] + cost);
}
}
int answer = Integer.MAX_VALUE;
for (int i = C; i < C+101; i++) {
answer = Math.min(answer, dp[i]);
}
System.out.println(answer);
}
}확실히 value마다 최소 비용을 저장하니 더 직관적이고 깔끔했다
번외 - 비용마다 최대 고객 수로 푼 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int C = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
final int MAXIMUM_BOUND = 100001;
int[] costs = new int[N];
int[] values = new int[N];
int[] dp = new int[MAXIMUM_BOUND]; // 비용이 i일 때 최대 고객
// Arrays.fill(dp, 100001);
// dp[0] = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
costs[i] = Integer.parseInt(st.nextToken());
values[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++){
int cost = costs[i];
for (int j = cost; j < MAXIMUM_BOUND; j++) {
dp[j] = Math.max(dp[j] ,dp[j - cost] + values[i]);
}
}
int answer = 0;
for (int i = 1; i < MAXIMUM_BOUND; i++) {
if(dp[i] >= C){
answer = i;
break;
}
}
// System.out.println(Arrays.toString(dp));
System.out.println(answer);
}
}