[백준] Gold IV. 호텔

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

 

문제

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

사용 알고리즘

• 회고

 

풀이

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

/*
    테이블: d[i]: i명을 유치할 때 투자하는 돈의 최소값
    점화식: d[i]: Math.min(d[i],
 */
public class Main {
    static int c, n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        int size = c + 101;
        int [] d = new int[size];

        for(int i = 1; i < size; i++) {
            d[i] = Integer.MAX_VALUE;
        }

        d[0] = 0;
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int pay = Integer.parseInt(st.nextToken());
            int people = Integer.parseInt(st.nextToken());

            for(int j = people; j < size; j++) {
                if (d[j - people] != Integer.MAX_VALUE)
                    d[j] = Math.min(d[j], d[j - people] + pay);
            }

        }

        int res = Integer.MAX_VALUE;
        for(int i = c; i < size; i++) {
            res = Math.min(res, d[i]);
        }
        System.out.println(res);
    }
}

 

 

회고

 

문제에서 적어도 C명 늘이기 위해 라는 멘트에 집중해서 봐야한다. C명이 초과되었을 때도, 가능하다는 이야기이다.

 

가령,

10 3
3 1
2 2
1 3

위 예시가 있을 때, 문제에서 요구하는 최소 고객 수는 10명이다.

 

범위를 10명부터 120명 (c + 101)까지 출력해보면,

6 5 4 7 6 5 8 7 6 9 8 7 10 9 8 11 10 9 12 11 10...

 

빨간색으로 칠한 숫자가 비용 1로 3명을 얻을 수 있는 경우이다. 

 

이렇게 c범위를 넘어서 계산하는 이유는, 1부터 c까지 최솟값을 갱신할 때 d[c]가 최솟값이 아닌 경우가 있기 때문이다. 위의 경우가 딱 그런 케이스다. 

 

나는 3,1 일때 d[9] = 3, 

2,2 일때 d[10] = 10,

1,3 일때 d[10] = 30

 

이렇게 되므로 Math.min(d[9] + 1, 10, 30). 근데 + 1얘를 어떻게 처리할 것인가? 계속 고민을 했었다. 그런데 c의 범위를 넓혀주면 해결되는 문제였다.

 

그리고,

if (d[j - people] != Integer.MAX_VALUE)

 

문제에서 이렇게 조건을 체크해줘야 하는데 만약에 d[j-people]이 MAX값이라면 갱신되지 않았으므로 계산을 하면 안된다.

 

d[j-people]이 MAX일때 pay를 더해주면 Integer Overflow가 나서 -MAX값으로 변한다. 처음에 왜 -값이 나오는지 이해를 못했는데, 오버플로우 때문에 그랬었다. 

 

얼마전에 풀었던 https://jschoi96.tistory.com/94 징검다리 건너기 문제에서도 MAX값이 아닐 때 체크를 해줬었다. 최소 비용이 갱신되었을 때만 다시 계산을 해야한다..!