[백준] 1106번. 호텔(JAVA)

문제

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

---

풀이(19분)

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

public class Main {

    static int n, c;
    static int[] minCost;

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

        minCost = new int[n + 101];
        Arrays.fill(minCost, Integer.MAX_VALUE);
        minCost[0] = 0;

        for (int i = 0; i < c; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int customers = Integer.parseInt(st.nextToken());

            for (int j = customers; j < n + 101; j++) {
                if (minCost[j - customers] != Integer.MAX_VALUE) {
                    minCost[j] = Math.min(minCost[j], cost + minCost[j - customers]);
                }
            }
        }

        int result = Integer.MAX_VALUE;
        for (int i = n; i < n + 101; i++) {
            result = Math.min(result, minCost[i]);
        }

        System.out.println(result);
    }
}

---

문제 풀이 전략

 

첫 번째 아이디어는 적어도 c라는 단어이다. 그 말은 c를 넘었을 때 c+1, c+2 인지에 관계없이 단순히 c+1이라고 생각해서 비용을 저장해 두면 되는 것이다.

즉, 100까지라고 했을 때 최종적으로 추가한게 105이던 110이던 101이라고 저장해 두고 사용하면 된다는 의미이다.

 

두 번째 아이디어는 dp이다. 사실 배열의 길이가 정해져 있다는 것을 알게 되었다면 dp라는 게 당연히 떠오를 수 있다.

 

minCost[0] = 0으로 초기화해 두고, 처음부터 시작하게 된다.

예를 들어 입력값인 3 5에 대해서는 min[5] = Math.min(minCost[5], 3 + minCost[0]) 이런 식으로 반복하며 dp 배열을 채워가게 되는 것이다.