1082 방 번호

문제 링크

문제 설명

첫 줄에 N이 (0<=N<=9) 가 주어진다. (사용할 수 있는 카드의 숫자들 개수) 두번 째 줄에 각 수 0~N 까지 숫자의 사용 비용이 주어진다. 세번 째 줄에 M이 주어진다.

주어진 조건에 맞춰 비용 상한 M에 맞추어 만들 수 있는 최대의 수를 구하라.

해결 전략

이 문제는 Greedy 와 Dynamic Programming 으로 해결이 가능하다. 둘 다 취약한 부분이라 우선 Greedy 방식으로 풀어 통과를 하였는데, 가정이 잘못되어 상당히 많은 시간을 소모하였다.

초기에 생각한 조건은 아래와 같았다.

1. 0이 아닌 수 중 최소 비용을 구하고, 해당 숫자를 구한다. 이 때 비용이 같다면 더 큰 숫자를 골라야 한다.
2. 해당 최소 비용의 수로 만들 수 있는 숫자 최대 길이를 구한다. 이 때 최소 비용에 해당하는 숫자로 최대한 많이 채우고, 비용이 남으면 0을 사용해본다.
3. 해당 길이 만큼의 정수 배열을 선언한다.
4. 배열을 최소 비용에 해당하는 숫자로 모두 채운다.
5. 배열의 첫자리부터 탐색을 시작한다. 이 때 주어진 숫자 카드 중 최대 수부터, 탐색하는 자리의 숫자 k보다 큰 수들에 대해 역순 탐색을 하며
   usable_cost = 남은 비용 + 현재 숫자 비용 - 변경하려는 숫자 비용 을 계산하고
   usable_cost >= 0 이라면 숫자를 변경하고 남은 비용을 업데이트 한다.
6. 반복문이 종료되면 숫자를 출력한다

위 조건으로 코드를 구현하면 예제로 주어진 입력에 대해서는 통과를 하였었다. 하지만 반례가 존재한다.

반례
4
1 2 2
5

위 조건대로 최대 수를 구해보면 다음과 같다.

0이 아닌 최소 비용은 2이며, 이에 해당하는 최대 숫자는 2이다. 이 상태로 배열 길이를 구해보면 비용이 1이 될 때 까지 2를 사용하면 4의 비용이 소모되고 남은 1의 비용으로 0을 채워, 길이 3의 배열을 만들 수 있다. 그 때 숫자는 220 이다. 하지만 2를 한번만 사용하고 나머지를 0으로 채운다면 2, 0, 0, 0 으로 네자리 숫자를 만들 수 있다.

따라서 위 조건에서 2번 조건과 4번 조건을 수정하여야 한다.

// 기존의 2, 4번 조건
2. 해당 최소 비용의 수로 만들 수 있는 숫자 최대 길이를 구한다. 이 때 최소 비용에 해당하는 숫자로 최대한 많이 채우고, 비용이 남으면 0을 사용해본다.
4. 배열을 최소 비용에 해당하는 숫자로 모두 채운다.
// 수정 후 2번 조건
2. 두가지 경우로 나눠 생각한다.
    a. 최소 비용이 0의 비용보다 작은 경우: 최소 비용에 해당하는 숫자를 이용하여 최대 길이를 구한다.
    b. 최소 비용이 0보다 큰 경우 : 최소 비용의 숫자는 한번만 사용하고, 나머지를 0으로 채워 최대 길이를 구한다.
4. 2-a 에 해당하면 전부 최소 비용에 해당하는 숫자로 배열을 채운다.
   2-b 에 해당하면 첫 자리만 최소 비용에 해당하는 숫자를 사용하고 나머지는 0으로 채운다.

위 조건에 맞추어 코드를 작성하면 문제를 해결할 수 있다.

소스코드

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) throws IOException {
        new Solution().run();
    }
}

class Solution {

    int N, M;

    List<Integer> prices = new ArrayList<>();

    public Solution() {
        Scanner scanner = new Scanner(System.in);
        N = Integer.parseInt(scanner.nextLine());
        String costs = scanner.nextLine();

        for(String cost : costs.split(" ")) {
            prices.add(Integer.parseInt(cost));
        }
        M = Integer.parseInt(scanner.nextLine());
        scanner.close();
    }

    private int[] getMinimumLengthArray(int minIndex, int cost) {
        int zeroCost = prices.get(0);

        int zeroLength = 0;
        int length = 0;

        if(zeroCost <= cost) {
            // 우선 0이 아닌 수를 하나 쓰고
            length++;
            M-=cost;
            // 나머지는 0으로 채워본다.
            while(true) {
                if(M - zeroCost >= 0) {
                    M-=zeroCost;
                    zeroLength++;
                    continue;
                }
                break;
            }
        } else {
            // 0은 고려할 필요가 없으므로
            while(true) {
                if(M-cost >= 0) {
                    M-=cost;
                    length++;
                    continue;
                }
                break;
            }
        }

        int[] ret = new int[length + zeroLength];

        for(int i = 0 ; i < length ; i++) {
            ret[i] = minIndex;
        }
        for(int i = 0 ; i < zeroLength ; i++) {
            ret[1 + i] = 0;
        }

        return ret;
    }

    // 0이 아닌 숫자 중 최소 비용을 구한다.
    private int getMinimumCost() {
        int minValue = Integer.MAX_VALUE;
        for(int i = 1 ; i < prices.size() ; i++) {
            minValue = Math.min(minValue, prices.get(i));
        }
        return minValue;
    }

    private int getMinimumCostNumber(int cost) {
        int idx = N-1;
        for( ; idx >= 1 ; idx--) {
            if(cost != prices.get(idx)) continue;
            break;
        }

        return idx;
    }

    private int getZeroCount() {
        int zeroPrice = prices.get(0);
        int count = 0;

        while(M > 0) {
            if(M - zeroPrice >= 0) {
                M-=zeroPrice;
                count++;
            }else{
                break;
            }
        }

        return count;
    }

    public void run() {
        // 기저 조건 처리
        if(N == 1) {
            System.out.println(0);
            return;
        }

        int minCost = getMinimumCost();
        if(minCost > M) {
            // 0이 아닌 수중 최소 비용이 현재 값보다 크다면
            // 0을 출력
            System.out.println(0);
            return;
        }

        int minIndex = getMinimumCostNumber(minCost);
        int[] answer = getMinimumLengthArray(minIndex, minCost);
        int minLength = answer.length;

        for(int i = 0 ; i < minLength ; i++) {
            int curNum = answer[i];
            int curCost = prices.get(curNum);

            for(int j = prices.size()-1 ; j > curNum ; j--) {
                int diff = M + curCost - prices.get(j); // 잔여 비용 + 현재 수의 비용 - 바꿀 수의 비용

                if(diff >= 0) {
                    // 이 경우 변경이 가능하다.
                    answer[i] = j;
                    M = diff;
                    break;
                }
            }

        }

        for(int i : answer) {
            System.out.print(i);
        }
        System.out.println();

    }
}

결과

회고

골드3라서 그렇게 어렵지 않을 것이라고 생각했는데 생각보다 많은 시간을 소비하였다. 잘못된 가정이었는데 단순히 산술적으로도 말이 안되는 조건이었음에도 반례조차 찾지 못해 많은 시간을 소비하였는데 조건에 대해 타당성을 검토를 잘 해야할 것 같다.