백준 1106번 : 호텔 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

호텔 골드 4

 

📖 문제

배낭문제

처음에는 우선 가격대비 효율이 가장 좋은 도시를 찾아서 

C / 도시의 고객수 * 가격 + C % 도시의 고객수 를 만족하는 모든 도시의 최소값을 구할라했으나

이는 불가능했다.

 

가격 대비 효율을 단순히 (고객수 - 가격) 순으로 내림차순 정렬하려했으나

4 9
1 5

 

위의 경우 4 9 가 더 효율이 좋다고 판단해버린다.

 

즉, 완전 잘못 설계했다. 

 

DP로 풀어야하는 문제이다. 

각 도시에 대하여 1~C 까지의 가격 최솟값을 구하면된다.

 

1. 현 도시의 홍보만으로 c를 채우는 경우

2. 현 도시의 홍보 1개만 사용하고 나머지 c를 다른 최솟값으로 채우는 경우

3. 이전 도시까지와 현재 도시를 비교하여 최솟값을 갱신

 

 

그런데 이 문제는 1차원 DP로도 충분히 풀 수 있다고 한다. 

그리고 범위도 C+99 까지 잡아야한다고 한다. '적어도 C 이상' 이라는 조건때문이다. 

하나의 도시로 C -1 까지 채웠을때 적어도 C이상이 될려면 하나의 도시를 더 추가해야한다.

이때 추가될 수 있는 최대 고객수는 100이기에  C-1+100 으로 최대 C+99까지 범위가 된다. 

 

 

---

🔅 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());


        int[] costs = new int[N + 1]; // 도시의 홍보 가격 
        int[] customers = new int[N + 1]; // 도시의 홍보 대비 얻는 고객 수 

        // 도시 , 1~C
        int[][] dp = new int[N + 1][C + 1];

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

        Arrays.fill(dp[0], Integer.MAX_VALUE);

        for (int c = 1; c <= C; c++) {
            for (int city = 1; city <= N; city++) {

                // city 홍보만 사용하여 c를 만족하는 경우
                int cnt = (int) Math.ceil((double) c / customers[city]);
                dp[city][c] = cnt * costs[city];

                // 현재 도시의 홍보 1개를 사용하면서 다른 최소값 홍보를 사용하는 경우
                if (c >= customers[city]) {
                    dp[city][c] = Math.min(dp[city][c], costs[city] + dp[N][c - customers[city]]);

                }
				
                // 이전 도시와 비교하여 최소값 갱신 
                dp[city][c] = Math.min(dp[city][c], dp[city-1][c]);
            }

        }

        System.out.println(dp[N][C]);
    }
}

 

🔅 문제 풀이 [1차원 DP]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        // 1~C+99
        int[] dp = new int[C + 100];

        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int customer = Integer.parseInt(st.nextToken());

            // customer ~ C+100 까지 (인덱스이므로 사실상 C+99)
            for (int j = customer; j < C + 100; j++) {
                dp[j] = Math.min(dp[j], cost + dp[j - customer]);
            }
        }


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

        System.out.println(answer);

    }
}

 

customer ~ MAX 까지 탐색한다.

현재 도시의 가격 + 남은 j명의 고객수를 채우는 최소비용

 

 

 

❗ 오답노트 / 필요한 지식

1.  바로 DP를 떠올리지 못한게 아쉽고, 2차원 DP를 (배낭) 구현하는데 좀 걸렸다.