[백준/Java] 1082 : 방 번호

백준 1082번 '방 번호' 풀이입니다. 예산 M으로 숫자를 구매해 만들 수 있는 가장 큰 수를 구하는 그리디 문제입니다. 자릿수가 길면 무조건 더 크므로, 먼저 자릿수를 최대화한 뒤 남은 돈으로 왼쪽 자리부터 더 큰 숫자로 업그레이드하는 방식으로 해결했습니다. 자릿수 최대화 후 자리 업그레이드라는 그리디 패턴을 새롭게 익혔습니다.

---

📌 문제 정보

• 번호: 1082
• 제목: 방 번호
• 난이도: Gold 3
• 분류: 그리디

---

💡 접근 방식

예산 M으로 숫자를 구매해 만들 수 있는 가장 큰 수를 구하는 문제로, 자릿수를 최대화한 뒤 왼쪽부터 값을 키우는 그리디로 해결했습니다.

1단계 - 최저가 숫자 찾기

• minFirst: 1~N-1 중 가장 싼 숫자 (첫 자리는 0 불가)
• min: 0~N-1 중 가장 싼 숫자 (자리 채우기용)

2단계 - 자릿수 최대화

• 첫 자리에 minFirst를 1개 구매
• 남은 돈으로 min을 최대한 많이 구매해 뒤에 채움

3단계 - 왼쪽부터 업그레이드

• 남은 돈으로 각 자리 숫자를 더 큰 숫자로 바꿀 수 있으면 교체

---

💻 핵심 코드

char[] digits = sb.toString().toCharArray();

for (int i = 0; i < digits.length; i++) {
    int cur = digits[i] - '0';

    for (int d = N - 1; d >= 0; d--) {
        if (i == 0 && d == 0) continue;

        int diff = p[d] - p[cur];
        if (diff <= money) {
            digits[i] = (char) ('0' + d);
            money -= diff;
            break;
        }
    }
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(L × N)
• 공간 복잡도: O(L)

---

📄 전체 코드

package B1082;

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

public class Main {
    static int N, M;
    static int[] p;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine().trim());
        p = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) p[i] = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine().trim());

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

        int min = 0;
        for (int i = 1; i < N; i++) if (p[i] < p[min]) min = i;

        int first = 1;
        for (int i = 2; i < N; i++) if (p[i] < p[first]) first = i;

        if (M < p[first]) { System.out.println("0"); return; }

        int money = M;
        sb.append(first);
        money -= p[first];

        int add = money / p[min];
        for (int i = 0; i < add; i++) sb.append(min);
        money -= add * p[min];

        char[] numbers = sb.toString().toCharArray();
        for (int i = 0; i < numbers.length; i++) {
            int cur = numbers[i] - '0';
            for (int j = N - 1; j >= 0; j--) {
                if (i == 0 && j == 0) continue;
                int diff = p[j] - p[cur];
                if (diff <= money) { numbers[i] = (char) ('0' + j); money -= diff; break; }
            }
        }
        for (char c : numbers) System.out.print(c);
    }
}