백준 - 호텔(1106)

오늘 풀어볼 문제는 ⭐호텔이란 문제이다!

1. 문제 요약

• 호텔 숙박객을 최소 c명 늘리기 위한 최소금액 찾기 (0<C<=1000)
• 필요한 돈, 증가 고객(max 100) 의 튜플 N개 존재 (0 < N <=20)
• 위 튜플은 정수배만큼 늘어날 수 있음.

2. 문제접근

[알고리즘]

• 고객의 수 만큼 dp 배열 money 생성
  • dp[i] = i의 금액 지불 시, 증가될 수 있는 최대 고객 수

• dp 배열을 처음->끝 까지 진행하며 다음을 확인
  • {필요돈, 증가 고객}일때, 현재 인덱스-필요돈>=0 면 다음 식 진행
    2.1.1 money[i] = Math.max(money[i-필요돈k] + 증가고객k);

• 계산 끝난 후 현재 고객 >= c라면 바로 로직 종료

3. 코드

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

class Info {
    int m;
    int p;

    public Info (int m, int p) {
        this.m = m;
        this.p = p;
    }
}
public class Main {
    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());

        List<Info> infos = new ArrayList<>();
        int [] money = new int[C+1];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            infos.add(new Info(m,p));
        }

        int answer = 0;

        for(int i=1; i<=C; i++) {
            for(Info now : infos) {
                if(i-now.m >=0) {
                    money[i] = Math.max(money[i-now.m] + now.p, money[i]);
                }
            }
            if(money[i]>=C) {
                answer=i;
                break;
            }
        }
        System.out.println(answer);
    }
}

결과는? 틀렸다! ㅋㅋ..; 바로 다음과 같은 반례 때문이다.

1000 1
100 1
0 (나의 답)
100000 (실제 답)

4. 틀린 이유

틀린 이유는 간단하다. 바로 범위 이슈이다.
현재 나는 int 배열을 C만큼이라고만 생각했다. 그러나 위 반례 같은 경우에서 알 수 있듯이 낼 수 있는 돈의 최대 금액은

원하는 인원의 최대 수(1000) * 최소 인원 1명 위한 최대 금액(100) 을 합친 100000이, 지불 가능한 최대 금액이다.

즉 int 배열 초기화를 100000로 하면 통과는 하지만 이건 실질적인 문제 해결방법이 아니었다.
범위가 더 커진다면 당연히 통과 못 할 알고리즘이다.

5. 또 다른 방법

위 방식에서 나의 dp 배열은 다음과 같다.

dp[i] = i의 금액 지불 시, 증가될 수 있는 최대 고객 수

그러나 이렇게 바꿔본다면?

dp[i] = i명의 고객을 유치하기 위한 최소 비용

5.1 알고리즘

• C+101 의 배열 생성
  • why? 하나의 도시에서 받을 수 있는 최대 인원 수는 100명이기에, 구하고자 하는 인원 수(C)에 +100 만 있어도 충분한 dp 배열!

• 위 dp 배열을 모두 Integer.MAX_VALUE;로 구성함.

• 하나의 튜플(필요금액, 증가인원)을 받고 나서 다음을 검사
  • for(int i=증가인원; i<=c+100; i++) {
    dp[i] = Math.min(dp[i], dp[i-증가인원]+필요금액);
    }
• 모든 튜플을 다 검사한 후, i=C부터 C+100까지 가장 작은 값이 정답임