[Java] 백준 1106 - 호텔 DP

호텔

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.
형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.
각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

import java.util.*;
import java.io.*;

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

        // 큰 값으로 지정 및 초기화 
        int INF = 1_000_000_000;
        dp = new int[c+100];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        
        for(int i = 0; i < n;i++) {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            for(int w = weight; w < dp.length;w++){
                dp[w] = Math.min(dp[w], dp[w - weight] + value);
            }
        }

        int answer = INF;
        for (int i = c; i < dp.length; i++) {
            answer = Math.min(answer, dp[i]);
        }
        System.out.println(answer);
    }
}

문제 분석

• DP 유형 중 요소를 여러 개 사용해도 되는 배낭 문제이다.

삽질한 이유

• DP문제를 풀 때마다 초기화하는걸 자꾸 까먹는다 .. 최솟값을 구하는 문제이므로 큰 값으로 초기화해주기
• 손님 수 이상이 되어도 상관 없고 적어도 c명 이상이라는걸 간과하고 처음에 dp 배열 크기를 잘못 잡았다.