[BOJ] 백준 1082번 : 방 번호 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1082

1082번: 방 번호

문제

이번에 VIP 회장으로 새로 부임한 백은진은 빅뱅의 위대함을 세계에 널리 알리기 위해서 사무실을 하나 임대했다.

빅뱅은 위대하기 때문에, 사무실의 번호도 되도록이면 커야 한다고 생각한다. 따라서 지금 가지고 있는 돈 전부를 가지고 방 번호를 만들려고 한다.

1층에 있는 문방구에서는 숫자를 판다. 각 숫자의 가격은 서로 다를 수 있기 때문에, 현재 가지고 있는 돈을 이용해서 만들 수 있는 가장 큰 숫자를 만들려고 한다.

예를 들어, 문방구에서 파는 숫자가 0, 1, 2이고, 각 숫자의 가격이 6, 7, 8이고, 백은진이 현재 가지고 있는 돈이 21이라면, 백은진이 만들 수 있는 가장 큰 수는 210(8+7+6=21)이다.

 

풀이

그리디 알고리즘을 적용하여 풀 수 있는 문제였습니다. 우리는 직관적으로 숫자의 자릿수가 길고, 맨 앞자리의 숫자가 클수록 전체적으로 큰 수라는 것을 알 수 있습니다. 따라서 위 2가지를 효율적으로 판단하는 로직을 전개하는 것이 관건이었습니다. 제가 생각한 로직은 다음과 같습니다.

1. 일단 비용이 낮으면서 가장 큰 숫자를 찾는다. (편의상, 이 숫자를 min이라고 하겠습니다.)

2. 입력받은 돈의 최대 한도까지, min만을 사용하여 가장 긴 숫자를 만든다.

3. 2번을 거치고 남은 돈의 액수에 따라, 새로 구입할 수 있는 숫자가 있는지 탐색한다. (이때, 큰 숫자부터 탐색)

4-1. 현재 자릿수에 해당하는 수보다 더 큰 숫자가 있다면, 돈을 지불하는 동시에 그 숫자로 바꾼다.

4-2. 구입할 수 있는 숫자가 없다면, min의 가격만큼 돈을 돌려받고 다음 자릿수로 넘어간다.

5. 만약, 모든 자릿수가 0이라면 그것은 숫자 0 만을 구입할 수 있다는 의미이므로 "000..."이 아닌 0 하나만 답으로서 출력한다.

위에 로직을 그대로 구현하면 되는데, 저는 자릿수를 초기화 해주는 char타입의 배열을 정의하였습니다. 그리고 자릿수의 시작점을 start라는 변수를 이용함으로써, 추가적으로 숫자를 구입할 수 없는 경우에는 start을 +1하는 방식으로 자릿수를 하나 넘겼습니다.

예제

N = 3 - 숫자의 개수

stationery = {5, 23, 24} - 0 ~ 2 숫자의 비용

money = 30 - 현재 갖고 있는 돈

위에서 설명한 풀이 방식대로 이 예제를 풀어보겠습니다.

먼저, 가장 비용이 작은 수는 0이고 비용이 5이므로, digits 배열은 {0, 0, 0, 0, 0, 0}이 될 것입니다. 이 과정에서 money = 0이 됩니다.

그리고 000000의 첫 번째 자릿수인 0을 1이나 2로 교체할 수 있는지 판단해 봅시다.

이때, 최종적인 답의 자릿수가 시작하는 인덱스 번호를 start라고 정의하였습니다.

0을 1이나 2로 교체한다는 말은 비용이 5인 숫자 0을 되팔아서 5원을 돌려받은 후, 비용이 23이나 24인 1또는 2를 새로 구입한다는 말입니다.

즉, stationery[i] <= money + 5가 성립하는지 가장 큰 숫자인 2부터 차례대로 검사합니다.

현재 money는 0원이므로 5원을 되판다고 해서 더 큰 숫자를 사는 것은 불가능합니다.

따라서, 첫 번째 자릿수에 해당하는 0을 되팔아서 5원을 확보한 뒤, 첫 번째 자릿수는 없는 것으로 판단하고 두 번째 자릿수로 건너뜁니다. 그리고 start을 1 증가시킵니다.

현재 5원을 가지고 있는 상태이고, 5원을 되판다고해서 추가적으로 1이나 2 숫자를 구매하는 것은 불가능합니다. 따라서, 숫자 0을 되팔고 세 번째 자릿수로 넘어갑니다. 그리고 start을 1 증가시킵니다.

이와 같은 방식으로 네 번째 자릿수까지는 새로운 숫자를 구매할 수 없으므로 0을 쭉 되팔면 현재 돈은 20원이 됩니다.

이제, 다섯 번째 자릿수는 무엇이 될 수 있는지 판단해 봅시다. (현재 start는 4인 상태입니다.)

money + 5를 하면, 25이므로 가장 큰 숫자인 2를 사는 것이 가능합니다. 따라서 이것을 구입함으로써 돈을 1원으로 감소하지만, digits 배열은 {0, 0, 0, 0, 2, 0}으로 바뀌게 됩니다. 이렇게 숫자를 새로 구매할 경우 start는 더이상 증가하지 않고, 이것으로 고정이 됩니다.

마지막 자릿수는 5원을 되판다고해서 추가적으로 숫자를 구입할 수 없으므로 이대로 탐색은 종료됩니다.

따라서, digits배열의 start 인덱스부터 끝까지 값을 출력하면 20이 되는 것을 알 수 있습니다.

 

자세한 소스코드는 아래를 참고하시면 되겠습니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
 
        int[] stationery = new int[N];
        int min = 50;
        int index = -1;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(st.nextToken());
            stationery[i] = temp;
 
            if (min >= stationery[i]) { // 일단 비용이 가장 작으면서 숫자는 큰 수를 찾는다.
                min = stationery[i];
                index = i;
            }
        }
 
        int money = Integer.parseInt(br.readLine());
        char[] digits = new char[51];
        int cnt = 0;
        while (money >= min) { // 비용이 가장 작으면서 숫자는 큰 수로 배열을 완성한다.
            digits[cnt++] = (char) (index + '0');
            money -= min;
        }
 
        int start = 0; // digits 배열에서 우리가 구하려는 답의 자릿수가 시작하는 위치.
        for (int i = 0; i < cnt; i++) {
            for (int j = N - 1; j >= 0; j--) {
                // 현재 돈에다가 min을 더한 값이 statinonery[j]보다 크다는 뜻은
                // 더 큰 숫자를 살 수 있다는 의미이다.
                if (stationery[j] <= money + min) {
                    digits[i] = (char) (j + '0');
                    money += min - stationery[j];
                    break;
                }
            }
 
            // digits[start]가 0이라는 뜻은
            // 현재 돈으로는 더 큰 숫자를 살 수 없다는 의미이다.
            // 따라서 자릿수를 1개 포기하고 min만큼의 돈을 다시 돌려 받는다.
            if (digits[start] == '0') {
                start++;
                money += min;
            }
        }
 
        // start와 cnt가 같다는 뜻은
        // digits 배열에서 cnt까지의 인덱스 값이
        // 모두 0이라는 의미이고, 이것은 0~N-1까지의 수 중에서
        // 오직 0만 구입할 수 있다는 것을 의미한다.
        if (start == cnt) {
            bw.write("0\n");
            bw.close();
            br.close();
            return;
        }
 
        String ans = "";
        for (int i = start; i < cnt; i++) {
            ans += digits[i];
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.