[백준] 1082. 방 번호

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

1082번: 방 번호

그리디 문제로, 주요 포인트는 다음과 같다.

• 가격이 싼 숫자를 우선으로 골라야 많은 숫자를 구매할 수 있어서 자릿수가 길어진다!
  • 그런데 가격이 가장 싼 숫자가 0(인덱스가 0)이라면, 맨 앞자리 수가 0이 되어 자릿수랑 무관하게 큰 숫자가 될 수 없다.
  • 따라서 가격이 가장 싼 숫자가 0이라면, 그 다음으로 싼 숫자를 제일 앞에 두고, 나머지 자릿수는 가장 싼 숫자를 둔다.
  • 반면 가격이 가장 싼 숫자가 0이 아니라면, 해당 숫자를 최대한 많이 고른다.
• 위 과정으로 최대한 긴 자릿수를 생성했다면, 각 자리수의 값을 큰 값으로 변경해줘야 한다.
  • 이때 제일 앞 자리부터 숫자를 변경해줘야 하고
  • 가장 큰 값들로 우선 변경해준다. (이때 현재 가진 돈으로 구매 가능한지 확인 필요)

그리디 아이디어를 생각하는 것이 좀 어려운 거 같다. 아이디어를 잘 생각하고, 구현을 실수 없이 잘 해야 한다.

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int m;
    static List<Card> input = new ArrayList<>();

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

        n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            input.add(new Card(i, Integer.parseInt(st.nextToken())));
        }
        m = Integer.parseInt(br.readLine());

        if (n == 1) {
            System.out.println(0);
            return;
        }

        // 가격이 싼 순서대로 정렬
        Collections.sort(input, new Comparator<Card>() {
            @Override
            public int compare(Card o1, Card o2) {
                return o1.cost - o2.cost;
            }
        });

        // 1. 가장 싼 숫자를 살 수 있는 만큼 사서 "자릿수 늘리기"
        List<Card> cards = new ArrayList<>();
        if (input.get(0).num == 0) {
            cards.add(input.get(1));
            m -= input.get(1).cost;
            while (m >= input.get(0).cost) {
                cards.add(input.get(0));
                m -= input.get(0).cost;
            }
        } else {
            while (m >= input.get(0).cost) {
                cards.add(input.get(0));
                m -= input.get(0).cost;
            }
        }

        // 2. "각 자리 수 변경하기" (앞자리부터, 큰 숫자로)
        int[] answer = new int[cards.size()];
        // 숫자가 큰 순서대로 정렬 (숫자가 같다면 가격이 싼 순서대로(싼 걸 먼저 사면 좋으니까))
        Collections.sort(input, new Comparator<Card>() {
            @Override
            public int compare(Card o1, Card o2) {
                if (o2.num == o1.num) {
                    return o1.cost - o2.cost;
                }
                return o2.num - o1.num;
            }
        });

        for (int i = 0; i < cards.size(); i++) {
            m += cards.get(i).cost;
            // 변경되지 않은 경우에는 기존 값 그대로
            if (!replace(i, answer)) {
                answer[i] = cards.get(i).num;
            }
        }
        for (int i : answer) {
            System.out.print(i);
        }
    }

    private static boolean replace(int idx, int[] answer) {
        for (int i = 0; i < input.size(); i++) {
            if (m < input.get(i).cost) {
                continue;
            }
            m -= input.get(i).cost; // 구매
            answer[idx] = input.get(i).num;
            return true;
        }
        return false;
    }

    static class Card {
        int num;
        int cost;

        public Card(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }
    }
}