[백준 1082] 방 번호 - JAVA

BOJ Link

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

 

풀이 과정

각 방 숫자별로 비용이 다를 때, 가지고 있는 돈으로 가장 큰 숫자를 구성하는  그리디 + DP문제다.

해당 풀이에서는 DP를 사용하지 않았다.

 

단순히 그리디하게 생각하면, 앞자리는 가능한 가장 큰 수여야 한다.

 

그러나, 반례가 있다.

2번의 비용이 10, 1번의 비용이 5라면, 10원으로 2혹은 11을 구성할 수 있다. 그러므로 마냥 앞자리가 가장 큰 수여선 안된다.

 

이를 해결하기 위해 now = (현재 남은돈 - i번째 숫자의 비용) / 숫자 비용의 최소값 으로 놓았다.

이는 곧 최소값만 사용했을 때,  i번째 숫자를 앞에 놓는다면 그 뒤로 now길이의 숫자를 놓을수 있다는 것을 의미한다.

이것으로 같은 길이의 숫자를 만든다면 가장 큰 수로, 더 큰길이의 숫자를 만든다면 더 작더라도 그 수로 갱신한다.

 

해당 과정을 반복하며, 맨 끝자리(1의 자리)수를 별도로 구해주면 끝이다.

문제에서, 번호가 0이 아닌이상 맨 앞자리는 0이 될 수 없으므로, 첫 탐색(맨 앞자리 탐색)일 때만 i=1부터 시작한다.

 

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int remain = Integer.parseInt(br.readLine());

        int min = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            min = Math.min(arr[i], min);
        }

        StringBuilder sb = new StringBuilder();

        boolean isFirst = true;

        while (true) {
            int maxl = 0;
            int num = -1;

            for (int i = isFirst ? 1 : 0; i < arr.length; i++) {

                int now = (remain - arr[i]) / min;
                if (now > 0 && now >= maxl) {
                    maxl = now;
                    num = i;
                }
            }

            isFirst = false;

            if (num == -1) break;
            sb.append(num);
            remain -= arr[num];
        }

        int num = -1;

        // 마지막 자리에 올 수 있는 수중 가장 큰 수 삽입
        for (int i = 0; i < arr.length; i++) {
            if (remain >= arr[i]) num = Math.max(i, num);
        }

        if (num != -1) sb.append(num);
        System.out.println(sb);
    }
}