백준 1082번 - 방 번호

문제

백준 1082번 - 방 번호

아이디어

가능한 큰 번호를 만들기 위해서는 수의 길이가 길고, 앞자리 수가 클수록 유리하다는 조건을 생각하면서 해결한다.

코드 구현 - 자바

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

public class BJ_1082 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] price = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            price[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());

        // 1
        int minCost = 50;
        int minNum = -1;
        for (int i = 0; i < n; i++) {
            if (price[i] <= minCost) {
                minCost = price[i];
                minNum = i;
            }
        }

        // 2
        int length = m / minCost;
        if (length == 0) {
            System.out.println(0); 
            return;
        }

        // 3
        int[] result = new int[length];
        Arrays.fill(result, minNum);
        m -= minCost * length; // 남은 돈

        // 4
        int s = 0;
        for (int i = 0; i < length; i++) {
            // 큰 수부터 탐색
            for (int j = n - 1; j >= 0; j--) {
                if (price[j] <= m + minCost) {
                    result[i] = j;
                    m += minCost;
					m -= price[j];
                    break;
                }
            }

            if (result[s] == 0) {
                s++;
                m += minCost;
            }
        }

        // 5
        if (s == length) {
            System.out.println(0);
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = s; i < length; i++) {
            sb.append(result[i]);
        }
        System.out.println(sb);
    }
}

1

• 가장 적은 비용으로 가장 큰 수를 살 수 있는 비용과 숫자를 구한다.

2

• M원으로 만들 수 있는 최대 자릿수를 계산한다.
• 가장 적은 비용이 드는 숫자로 M원을 모두 소모하면 가장 긴 수를 만들 수 있다.

3

• 만들 수 있는 가장 긴 자릿수를 가장 적은 비용이 드는 숫자로 모두 초기화한다.
• 그리고 M원은 모두 사고 남은 돈으로 수정해준다.

4

• 앞자리부터 큰 숫자를 살 수 있는지 확인한다.
• 큰 수부터 역으로 탐색하면서 해당 숫자를 살 수 있으면 대체한다.
• 그리고 남은 돈을 갱신해야 하는데, 현재 모든 자리는 가장 적은 비용의 수로 모두 채워져 있다.
• 따라서 가장 적은 비용의 수를 팔기 때문에 돈을 다시 받고, 가능한 큰 수로 대체하는 것이기 때문에 큰 수의 비용으로 사는 것이다.
• 그리고 최종 숫자는 0으로 시작하면 안되기 때문에 맨 앞자리부터 수가 0이면 의미가 없으므로 돈을 다시 받을 수 있다.

5

• 맨 앞 자리 수가 0이 아닌 유효한 시작 부분부터 숫자를 출력한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)