[JAVA] boj 1082 방 번호

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

1082번: 방 번호

문제

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해야 한다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. M원을 모두 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다.

출력

첫째 줄에 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

제한

• 1 ≤ N ≤ 10
• 1 ≤ Pi ≤ 50
• 1 ≤ M ≤ 50
• N, Pi, M은 정수

예제 입력 1

3
6 7 8
21

예제 출력 1

210

예제 입력 2

3
5 23 24
30

예제 출력 2

20

예제 입력 3

4
1 5 3 2
1

예제 출력 3

0

예제 입력 4

10
1 1 1 1 1 1 1 1 1 1
50

예제 출력 4

99999999999999999999999999999999999999999999999999

문제 풀이

다이나믹 프로그래밍으로 문제를 해결하였다.

 

처음에는 번호가 0~9 까지 밖에 없어서 경우의 수가 그렇게 많지 않을 것이라고 생각해서 단순히 dfs로 코드를 작성하였는데 최대 숫자의 길이가 50이고 0~9까지 숫자를 모두 사용한다면 10의 50제곱이라는 엄청난 연산을 수행하게 된다는 것을 알았다.

 

그래서 숫자가 큰 숫자를 먼저 입력하도록 하고 숫자의 길이가 같을 때 지불한 가격이 같거나 크다면 연산을 멈추도록 탐욕 알고리즘으로 풀이를 했지만 그 연산은 여전히 적지가 않았다.

 

결론적으로 다이나믹 프로그래밍을 활용하였고 0~M까지 가격을 기준으로 배열을 만들어 해당 가격에서의 최대 값을 만들어 가도록 코드를 작성하였다.

 

코드

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

public class Main_BJ_1082_방번호 {

  static String[] dp;
  static int N;
  static int[] cost;
  static int price;

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    N = Integer.parseInt(br.readLine());
    dp = new String[51];
    Arrays.fill(dp, "");
    cost = new int[10];

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

    for (int i = 0; i <= price; i++) {
      for (int j = N - 1; j >= 0; j--) {
        if (i - cost[j] < 0)
          continue;

        for (int k = 0; k < dp[i - cost[j]].length(); k++) {
          if (dp[i - cost[j]].charAt(k) - '0' < j) {
            String t = dp[i - cost[j]].substring(0, k) + String.valueOf(j) + dp[i - cost[j]].substring(k);
            if (dp[i].length() < t.length())
              dp[i] = t;
            else if (dp[i].length() == t.length())
              dp[i] = compare(dp[i], t);
          }
        }
        if (dp[i - cost[j]].length() == 0 && j == 0)
          continue;

        String t = dp[i - cost[j]] + String.valueOf(j);
        if (dp[i].length() < t.length())
          dp[i] = t;
        else if (dp[i].length() == t.length())
          dp[i] = compare(dp[i], t);
      }
    }
    if (dp[price].length() == 0)
      System.out.println("0");
    else
      System.out.println(dp[price]);
  }

  static String compare(String n1, String n2) {
    for (int i = 0; i < n1.length(); i++) {
      if (n1.charAt(i) == n2.charAt(i))
        continue;
      else if (n1.charAt(i) > n2.charAt(i))
        return n1;
      else
        return n2;
    }
    return n1;
  }
}