[JAVA] 백준 1106번 : 호텔

https://www.acmicpc.net/problem/1106

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        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[] cost = new int[N];
        int[] cnt = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            cost[i] = Integer.parseInt(st.nextToken());
            cnt[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[C + 100];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < dp.length; j++) {
                if(dp[j] == Integer.MAX_VALUE) continue;
                int tmp = j + cnt[i];
                if(tmp < C + 100)
                    dp[tmp] = Math.min(dp[tmp], dp[j] + cost[i]);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = C; i < C+100; i++) {
            ans = Math.min(ans, dp[i]);
        }

        System.out.println(ans);
    }
}

💡 DP

풀이

• p원을 들어서 c명의 고객을 불러들이는 구조, 이때 정수배도 가능하다
• 결국 c의 가치를 가지고 무게가 p인 짐을 넣는 가방문제와 동일한 구조 (이때 물건은 무한개 가능)
  • 가치가 C 이상인 경우의 수 중 최소 무게를 가지는 경우를 출력하는 방식

dp[c] = p : c명의 고객을 확보하기 위한 최소 비용 p

 

- 이때 dp 범위를 결정하는게 중요하다. 범위를 0 ~ C+100으로 설정해준다.

   - 최악의 경우를 생각해보자, 현재까지 dp[C-1]이 최선인 상황이다. 이때 설상가상 (100명, 비용 1원)이 존재하는 상황이다. 

   -> 이 경우 100명을 플러스 한다고 쳐도 인원의 최대값은 c + 99다. 즉 c + 100 이상의 범위는 고려할 필요가 없다는 것

- dp를 MAX_VALUE로 초기화 해준다 (min 연산을 사용해야 하므로), dp[0]은 0으로 초기화

 

- 모든 경우 (p, c)에 대해서 dp에 대해 0 ~ C + 100 까지 for문 돌림, j에 대해 dp[j + c] 값을 dp[j] + p로 갱신

    - dp[j] = MAX인 경우 : 해당 경우 j명을 확보하는 것은 (p, c)로는 불가능하므로 pass

    - j + c < C + 100 인 경우에만 진행 : 기존 값과 새로운 값 (dp[j] + p) 중 작은 값으로 갱신