[백준]#1106 호텔
문제
세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.
형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
예를 들어, “어떤 도시에서 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
풀이
이 문제는 DP(다이나믹 프로그래밍) 알고리즘을 이용해서 풀 수 있었다. DP문제가 부족하다고 생각해서 연습중입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N;
static int C;
static Pair[] arr;
static int[] dp;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
C = Integer.parseInt(input[0]);
N = Integer.parseInt(input[1]);
arr = new Pair[N];
dp = new int[C+1];
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
arr[i] = new Pair(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
}
System.out.println(dfs(C));
}
public static int dfs(int temp) {
if(temp<=0) return 0;
if(dp[temp]!=0) return dp[temp];
int min = Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
Pair p = arr[i];
min = Math.min(min, dfs(temp-p.num) + p.cost);
}
return dp[temp] = min;
}
public static class Pair {
int cost;
int num;
public Pair(int cost, int num) {
this.cost = cost;
this.num = num;
}
}
}
Author And Source
이 문제에 관하여([백준]#1106 호텔), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준1106-호텔저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)