https://www.acmicpc.net/problem/1106
1106번: 호텔
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때
www.acmicpc.net
코드설명
배낭문제(Knapsack) + DP(Dynamic Programming) 문제입니다.
문제로직입니다.
1. DP[C+100] 는 각 호텔고객의 수를 늘릴때 사용한 돈의 최솟값입니다. 여기서 C+100 으로 처리하는 이유는 각 도시에서 얻을 수 있는 고객의 수가 100 보다 작거나 같기 때문입니다.
예로들면, 각 도시에서 만약에
1원으로 100명을 얻고
2원으로 80 명을 얻는경우가 있다고 가정합니다.
이떄 C가 300 이라고 해봅니다. 이렇다면, 1원을 4번 사용하여 400명을 얻었다고 가정해봅니다. 이떄, 1원을 3번 사용하여 300명을 얻든 1원을 4번 사용하여 400명을 얻든 500명을 얻든간에 300명부터 400명까지만 고려했을떄 최소값이기만 하면 되므로 C+100 을 하는 것입니다.
2. 문제예시로봤을때, 어떻게 3원으로 5명을 늘리는경우와 1원으로 1명 늘리는 경우의 최소값을 구할 수 있을까라는 것이 DP의 핵심입니다.
12 2
3 5
1 1- 예로들면,
- 먼저 3 5 인 경우를 살펴보겠습니다.
- DP[5] = 3, DP[10] = 6, DP[15] = 9 .... 생략 이 될 것입니다.
- 이제 1 1 인 경우를 살펴보겠습니다.
- DP[1] = 1, DP[2] = 2, DP[3] = 3, DP[4] = 4, DP[5] = 3, DP[6] = 4
- 위의 DP의 경우에서 보이듯이 이미 DP[5], 5명의 고객을 모으는데 3원이라는 최소값이 있으므로 6명의 고객을 모을떄는 6이 아닌 DP[5] + 1 로써 DP[6] = 4 , 즉 최소의 돈으로 6명의 고객을 모을 수 이습니다.
위의 로직을 코드로 표현하면
for(int j=peopleCnt; j<C + 100; j++) {
if (dp[j-peopleCnt] != Integer.MAX_VALUE)
dp[j] = Math.min(dp[j], cost + dp[j-peopleCnt]);
}
3. 문제에서 적어도 C명을 구하는것이 목적으로 C ~ C+100 까지의 최소값을 구하면 답입니다.
for(int i=C;i<C+100;i++) {
answer = Math.min(answer, dp[i]);
}위와 같이 바텀업 방식으로 풀어도 되지만, 탑다운 방식으로도 풀어보았습니다.
탑다운 방식으로 접근할경우, 비용의 최대값을 선택하는 부분에 있어서 틀렸습니다.
문제에 대한 이해가 부족하였습니다. 처음에는 최대값을 101*20 + 1 로 처리했었지만, 만약 1000 명의 사람이 필요할때, 100의 비용으로 1명씩 데려올 수 있다면, 100 * 1000 이 최대값이 될 것 입니다.
문제에서 주어진 입력값을 보면
. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.
40퍼에서 틀렸습니다.(최대값 설정 실패)
1000 1
100 1
결과 : 0
정답 : 100000
만약 위와 같이 생각하기 싫다면, 아래와 같이 Integer.MAX_VALUE를 사용하고 실패시 MAX/2 를 사용할 수 있습니다.
public static int answer = Integer.MAX_VALUE;
public static int MAX = Integer.MAX_VALUE; //최대 요금값.
...
if(level>=N) {
return MAX/2;
}
...유의할점은, 이 문제에서 나올 수 있는 최대값의 비용 = ( 1000(원하는 최대 인원) / 1 (홍보를 통해 얻을 수 있는 인원 : 1) ) * 100 ( 해당 홍보를 통해 얻을 수 있는 인원을 위한 최대 비용 ) 입니다.
= 1000 * 100
이 문제에서 만일 simulate(level, people, cost)로 진행할경우 손쉽게 정답을 구할 수 있을 것 입니다.
하지만, 메모리제이션 및 DP를 활용하지 못합니다. 메모리제이션은 항상 같은 입력에 대해 같은 OUTPUT이 나와야만 적용할 수 있습니다. 만약, 3개의 인자 level, people, cost를 활용할경우 같은 인자에 대해 다른 인자값이 적용되는경우가 있으므로 활용하지 못합니다.
정리해보자면, 메모리제이션을 적용하려면 같은 상태에 대해 항상 같은결과를 반환하는 함수가 필요합니다. 즉, 같은 인자에 대해 항상 같은 결과를 반환해야합니다.
최적화를 진행한 부분은, 아래의 주석 함수 호출 부분입니다.
해당 동시에 홍보하고, 다음 도시로 넘어가는 경우는 필요없습니다.
이유는, 다음 도시로 넘어간뒤 다시 재귀가 실행되기 때문에 그렇습니다.
이 문제에서 해당 로직이 있었어도 상관이 없었던 이유는 최솟값을 찾는 것이 목표였기 때문입니다.
//해당 도시에 홍보하고, 다시 한번 홍보하려는 경우
resultA = city[level].cost + simulate(level, customer - city[level].customer);
//이 경우는 필요없다. 다음으로 넘어가게 되면, 어처피 resultA에서 다시 검사한다.
//해당 도시에 홍보하고, 다음 도시로 넘어가는 경우
//resultB = city[level].cost + simulate(level + 1, customer - city[level].customer);
//선택하지 않고 넘어가는 경우
resultC = simulate(level + 1, customer);코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int C, N;
public static long answer = Integer.MAX_VALUE;
public static int[] arr, brr;
public static int[] dp;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
// 각 고객을 늘렸을때 투자해야하는 돈의 최솟값
// 적어도 C명을 늘려야하므로 그보다 더 많이 고객을 늘렸을떄의 비용이 더 작을 수도 있으므로 고객의 개수
// 한번에 얻을 수 있는 고객의 수는 100 이하입니다.
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 peopleCnt = Integer.parseInt(st.nextToken());
for(int j=peopleCnt; j<C + 100; j++) {
if (dp[j-peopleCnt] != Integer.MAX_VALUE)
dp[j] = Math.min(dp[j], cost + dp[j-peopleCnt]);
}
}
for(int i=C;i<C+100;i++) {
answer = Math.min(answer, dp[i]);
}
System.out.println(answer);
}
}탑다운방식에서 불필요한 재귀를 찾고서, 최적화했습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N;
public static int answer = 0;
public static City[] city;
// 1000 20
// 100 1
// 1000 * 100 = 최대값
public static int MAXVALUE = 1001 * 101 + 1;
public static int[][] dp;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
city = new City[N];
dp = new int[21][1001];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
int inputCost = Integer.parseInt(st.nextToken());
int inputCustomer = Integer.parseInt(st.nextToken());
city[i] = new City(inputCost, inputCustomer);
}
answer = simulate(0, C);
System.out.println(answer);
}
public static int simulate(int level, int customer) {
if(customer <= 0) { // 적어도 C명 늘이는 경우
return 0;
}
if(dp[level][customer] > 0) {
return dp[level][customer];
}
if(level >= N) { //만약 범위를 벗어난다면, 해당 방법에서는 더이상 못찾는다는 의미입니다. 그러므로 최대값 반환하여 무효화시킵니다.
return MAXVALUE;
}
int resultA = MAXVALUE, resultC = MAXVALUE;
//해당 도시에 홍보하고, 다시 한번 홍보하려는 경우
resultA = city[level].cost + simulate(level, customer - city[level].customer);
//이 경우는 필요없다. 다음으로 넘어가게 되면, 어처피 resultA에서 다시 검사한다.
//해당 도시에 홍보하고, 다음 도시로 넘어가는 경우
//resultB = city[level].cost + simulate(level + 1, customer - city[level].customer);
//선택하지 않고 넘어가는 경우
resultC = simulate(level + 1, customer);
return dp[level][customer] = Math.min(resultA, resultC);
}
}
class City {
int cost;
int customer;
public City() {
}
public City(int cost, int customer) {
this.cost = cost;
this.customer = customer;
}
}
탑다운 방식 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int C, N;
public static int answer = 0;
public static City[] city;
public static int MAXVALUE = 1001 * 101 + 1;
public static int[][] dp;
// 1000 20
// 100 1
// 1000 * 100 = 최대값
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
city = new City[N];
dp = new int[21][1001];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
int inputCost = Integer.parseInt(st.nextToken());
int inputCustomer = Integer.parseInt(st.nextToken());
city[i] = new City(inputCost, inputCustomer);
}
answer = simulate(0, C);
System.out.println(answer);
}
public static int simulate(int level, int customer) {
if(customer <= 0) { // 적어도 C명 늘이는 경우
return 0;
}
if(dp[level][customer] > 0) {
return dp[level][customer];
}
if(level >= N) { //만약 범위를 벗어난다면, 해당 방법에서는 더이상 못찾는다는 의미입니다. 그러므로 최대값 반환하여 무효화시킵니다.
return MAXVALUE;
}
int resultA = MAXVALUE, resultB = MAXVALUE, resultC = MAXVALUE;
//해당 도시에 홍보하고, 다시 한번 홍보하려는 경우
resultA = city[level].cost + simulate(level, customer - city[level].customer);
//해당 도시에 홍보하고, 다음 도시로 넘어가는 경우
resultB = city[level].cost + simulate(level + 1, customer - city[level].customer);
//선택하지 않고 넘어가는 경우
resultC = simulate(level + 1, customer);
return dp[level][customer] = Math.min(resultA, Math.min(resultB, resultC));
}
}
class City {
int cost;
int customer;
public City() {
}
public City(int cost, int customer) {
this.cost = cost;
this.customer = customer;
}
}탑다운 방식 1.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M, C;
public static City[] city;
public static int[][] DP;
public static int answer = 101*1001 + 1;
public static int MAX = 101*1001 + 1; //최대 요금값.
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
city = new City[N];
DP = new int[21][20*101];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
int inputCost = Integer.parseInt(st.nextToken());
int inputPeople = Integer.parseInt(st.nextToken());
city[i] = new City(inputCost, inputPeople);
}
answer = simulateByPeople(0, C);
System.out.println(answer);
}
public static int simulateByPeople(int level, int people) {
//만약 모든 사람을 채웠다면, 더이상 비용이 필요없으므로 0 을 반환합니다.
if(people <= 0) {
return 0;
}
//이미 계산한 적이 있다면,
if(DP[level][people] > 0)
return DP[level][people];
//만약 초과했다면, 해당 방법으로는 불가능한 방법입니다.
//return 0 을 할경우 resultCostC 입장에서 비용의 최소값이 0 이 나오므로 최대값을 넣어줍니다.
if(level>=N) {
return MAX;
}
int resultCostA = MAX, resultCostB = MAX, resultCostC = MAX;
resultCostA = city[level].cost + simulateByPeople(level, people - city[level].people);
resultCostB = city[level].cost + simulateByPeople(level + 1, people - city[level].people);
resultCostC = simulateByPeople(level + 1, people);
return DP[level][people] = Math.min(resultCostA, Math.min(resultCostB, resultCostC));
}
}
class City{
int cost;
int people;
public City() {
}
public City(int cost, int people) {
this.cost = cost;
this.people = people;
}
}