bj1082(방 번호)-그리디

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

진짜 어려운 문제다.

어렵다기보단, 예외 케이스가 많이 나올 수 있는 문제였다.

 

0이 맨앞에 올 수 없다는 거에서 막혔다.

 

그리디 전략은

1. 일단 가장 큰 자릿수가 가장 큰 수이기에 가장 작은 가격을 가진 번호로 max 자릿수를 구한다.

=> 가장 작은 가격을 가진 번호가 0일 때, 최소 하나(맨 앞 자릿수)는 0이 아닌 수가 들어가야하기에, 두번째 작은 가격을 가진 수를 구한다.(여기서, 조금 복잡해진다.)

2. 큰 번호 부터 정렬한다.

3. 만약, 이 큰 번호를 샀을 때, 자릿수가 줄어든다면, 이는 버린다.

4. 즉, 자릿수에 맞게 살 수 있는 큰 번호부터 사는 것이 이 문제의 그리디 전략이다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static List<int[]> nums = new ArrayList<>();
    static List<Integer> answers = new ArrayList<>();
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stringTokenizer;
    public static void main(String[] args) throws IOException {
        initialize();
        solve();
        print();
    }

    private static void print() {
        if(answers.isEmpty()){
            System.out.println(0);
            return;
        }
        for(int t : answers){
            System.out.print(t);
        }
    }

    private static void solve() {
        firstSort();
        int cheapestNum = nums.get(0)[0];
        int cheapestValue = nums.get(0)[1];
        if(nums.size() == 1)return;
        int secondNum = nums.get(1)[0];
        int secondValue = nums.get(1)[1];
        secondSort();

        int digits = getDigits(cheapestNum, cheapestValue, secondNum, secondValue);
        int tDigits = digits;
        int remainValue = M;
        for(int i = 0; i < digits; i++){
            for(int j = 0; j < nums.size(); j++){
                int tempNum = nums.get(j)[0];
                int tempValue = nums.get(j)[1];
                if(i == 0 && tempNum == 0)continue;
                if(remainValue - tempValue >= 0 && (remainValue - tempValue) / cheapestValue + 1 == tDigits){
                    tDigits--;
                    answers.add(tempNum);
                    remainValue -= tempValue;
                    break;
                }
            }
        }
    }

    private static int getDigits(int cheapestNum, int cheapestValue, int secondNum, int secondValue) {
        if(cheapestNum == 0){
            return (M - secondValue) / cheapestValue + 1;
        }
        return M / cheapestValue;
    }

    private static void secondSort() {
        nums.sort((o1, o2) -> o2[0] - o1[0]);
    }

    private static void firstSort(){
        nums.sort((o1, o2) -> {
            if(o1[1] > o2[1]) return 1;
            if(o1[1] < o2[1]) return -1;
            if(o1[0] > o2[0]) return 1;
            return 0;
        });
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            nums.add(new int[]{i, Integer.parseInt(stringTokenizer.nextToken())});
        }
        M = Integer.parseInt(bufferedReader.readLine());
    }
}