[JAVA] boj 1106 호텔

문제 링크 : https://www.acmicpc.net/problem/1106

1106번: 호텔

문제

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1

12 2
3 5
1 1

예제 출력 1

8

예제 입력 2

10 3
3 1
2 2
1 3

예제 출력 2

4

예제 입력 3

10 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

예제 출력 3

10

예제 입력 4

100 6
4 9
9 11
3 4
8 7
1 2
9 8

예제 출력 4

45

문제 풀이

dfs와 다이나믹 프로그래밍을 이용하여 문제를 풀었다.

 

2차원 배열에 홍보하는 비용과 늘어나는 고객의 수를 저장하고 재귀를 돌면서 현재까지 금액을 dp배열에 저장한다. 사용한 금액이 dp배열에 존재하면서 해당 금액이 현재 금액보다 작다면 더 이상 진행하여도 최소 금액일 수 없기 때문에 return하는 방식으로 구현하였다.

코드

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

public class Main_BJ_1106_호텔 {
  static int[][] arr;
  static int C, N, ans;
  static int[] dp;

  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());

    arr = new int[N][2];
    int max = 0;

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());

      arr[i][0] = Integer.parseInt(st.nextToken());
      arr[i][1] = Integer.parseInt(st.nextToken());

      max = Math.max(max, arr[i][0]);
    }

    ans = Integer.MAX_VALUE;
    dp = new int[1101];

    Arrays.fill(dp, Integer.MAX_VALUE);

    dfs(0, 0);

    System.out.println(ans);
  }

  static void dfs(int cnt, int cost) {
    if (dp[cnt] > cost) {
      dp[cnt] = cost;
    } else {
      return;
    }
    if (cost >= ans) {
      return;
    }
    if (cnt >= C) {
      ans = Math.min(ans, cost);
      return;
    }

    for (int i = 0; i < N; i++) {
      dfs(cnt + arr[i][1], cost + arr[i][0]);
    }

  }
}