자바 - 백준 1106 / 호텔

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

골드4

구현 방법

전형적인 DP 유형이라고 생각이 들었습니다. knapsack 유형과 비슷하기도 했기 때문입니다.

풀이 방법은 dp 배열을 만들고 채울 수 있는 인원의 비용과 현재 비용을 비교하면서 최소값을 업데이트 하는 방식으로 구현했습니다.

점화식

dp[현재 인원 + 채울 수 있는 인원] = Math.min(dp[현재 인원 + 채울 수 있는 인원] , dp[현재 인원] + 채울 수 있는 인원 cost)

 

이때 주의할 점은 목표 인원을 넘더라도 비용이 더 작은 경우를 고려해야 한다는 점 입니다.

코드

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

/**
* 백준 1106
* 호텔
* 골드4
* https://www.acmicpc.net/problem/1106
*/
public class Boj1106 {

    private static class City {
        int cost;
        int people;

        public City(int cost, int people) {
            this.cost = cost;
            this.people = people;
        }
    }
    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()); // 도시 수

        City[] cities = new City[N];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int person = Integer.parseInt(st.nextToken());
            cities[i] = new City(cost, person);
        }

        int len = C + 101;
        int[] dp = new int[len];
        Arrays.fill(dp, 100001);
        dp[0] = 0;

        for(int i = 0; i < len; i++) {
            for(City c : cities) {
                int next = i + c.people;
                if(next < len) {
                    dp[next] = Math.min(dp[next], dp[i] + c.cost);
                }
            }
        }

        int answer = dp[C];
        for(int i = C + 1; i < len; i++)
            answer = Math.min(answer, dp[i]);

        System.out.println(answer);
    }
}