[BOJ_1106] 호텔

설명

---

DP를 활용한 문제이고 이때, 들어오는 도시마다 최소한 투자를 통해서 내가 만들어야하는 고객치를 딱 도달하는 것이 포인트 였습니다. 따라서, DP의 인덱스를 내가 최소한의 투자를 통해서 만들 수 있는 고객 유치 한계점으로 잡고 문제에 따른 조건을 만들었습니다.

 

나름 깔끔하게 메서드 별 역할을 나눠서 행동하게끔 구성을 해보았는데 생각보다는 별로네요. 좀 더 효율적으로 나누는 방법을 고려하는 것도 좋을 것 같습니다.

 

코드

---

package BOJ.Dynamic_Programming;

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

public class BOJ_1106 {
    static class City {
        int money;
        int numOfCostomer;
        public City(int money, int numOfCostomer){
            this.money = money;
            this.numOfCostomer = numOfCostomer;
        }
    }
    static City[] cities;
    static int dp[];
    static int C,N;
    private static void input() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        C = Integer.parseInt(tk.nextToken());
        N = Integer.parseInt(tk.nextToken());

        int money,numOfCostomer = 0;

        cities = new City[N];
        dp = new int[C + 1000001];

        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            money = Integer.parseInt(tk.nextToken());
            numOfCostomer = Integer.parseInt(tk.nextToken());
            cities[i] = new City(money,numOfCostomer);
        }
    }
    public static void main(String[] args) throws Exception{
        int ans = Integer.MAX_VALUE;
        input();

        for (int j = 0; j < N; j++){
            int k = cities[j].money;
            for (int i = 0; i < dp.length; i++){
                if(i - k < 0){
                    continue;
                }
                if(dp[i] < dp[i - k] + cities[j].numOfCostomer){
                    dp[i] = dp[i - k] + cities[j].numOfCostomer;
                }
                if(dp[i] >= C && ans > i){
                    ans = i;
                }
            }
        }
        System.out.println(ans);
    }
}

 

1106번: 호텔