[BOJ] 1038 - 감소하는 수 (G5)

suhyun·2022년 11월 23일
0

백준/프로그래머스

목록 보기
37/81

문제 링크

1038-감소하는 수


입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.


출력

첫째 줄에 N번째 감소하는 수를 출력한다.


문제 풀이

우선 n이 10보다 작다면 그대로 출력하면 되는거고
{0,1,2,3,4,5,6,7,8,9}에 대응되는 감소하는 수는 2^10-1개 이다.

다음으로 그 사잇값들에 대해 처리하는 방법인데

1: 1 10
2: 2 20 21 210
3: 3 30 31 32 310 320 321
뭐 이런식으로 만들 수 있기때문에 이거를 함수로 표현한게 makeList


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

public class Main {
    static ArrayList<Long> arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        arr = new ArrayList<>();

        if(n<=10) System.out.println(n);
        else if (n > 1022) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < 10; i++) {
                makeList(i, 1);
            }
            Collections.sort(arr);
            System.out.println(arr.get(n));
        }
    }
    
    // n:4
    // arr.add(0), arr.add(1), arr.add(2), arr.add(3), ... , arr.add(9)
    // arr.add(10)
    // arr.add(20), arr.add(21)
    // arr.add(30), arr.add(31), arr.add(32)
	// ...    

    static void makeList(long num, int idx) {
        if(idx>10) return;

        arr.add(num);
        for (int i = 0; i < num % 10; i++) {
            makeList((num * 10) + i, idx + 1);
        }
    }
}
profile
꾸준히 하려고 노력하는 편 💻

0개의 댓글