728x90
문제
세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.
형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.
각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
12 2
3 5
1 1
예제 출력 1
8예제 입력 2
10 3
3 1
2 2
1 3
예제 출력 2
4
예제 입력 3
10 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
예제 출력 3
10
예제 입력 4
100 6
4 9
9 11
3 4
8 7
1 2
9 8
예제 출력 4
45
알고리즘 분류
접근 방법
각 도시마다 1)홍보를 할 것인지 2)홍보를 하지 않을 것인지 를 정해야한다.
import java.util.*;
import static java.lang.Math.min;
public class BOJ_1106_호텔 {
static class Info{
int cost, customer;
public Info(int _cost, int _customer){
this.cost = _cost;
this.customer = _customer;
}
}
static int func(int N, Info[] arr, int targetC){
int[] dp = new int[1101];
Arrays.fill(dp, 100000);
dp[0] = 0;
for(int i = 0; i<N; i++){
for(int j = 1; j<=1100; j++){
if(j - arr[i].customer > -1){
dp[j] = min(dp[j], dp[j-arr[i].customer] + arr[i].cost);
System.out.println(dp[j]);
}
}
}
int ans = dp[targetC];
//최소 C명을 구하는 것. C명 이상 고객을 구했을 때 더 최소 비용이 될 수도 있음
for(int i = targetC+1; i<=1100; i++){
ans = min(ans, dp[i]);
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int C = sc.nextInt();
int N = sc.nextInt();
//ArrayList<Info> arr = new ArrayList<>();
Info[] arr = new Info[1200];
for(int i = 0; i<N; i++){
int cost = sc.nextInt();
int customer = sc.nextInt();
arr[i] = new Info(cost, customer);
}
int answer = func(N, arr, C);
System.out.println(answer);
}
}
참고/ 출처 : https://kangwlgns.tistory.com/97
728x90