💜 백준 1038 감소하는 수

1. 문제 분석

감소하는 수 문제 링크

321, 952 등 제일 큰 자릿수부터 작은 자릿수로 올수록, 자릿수의 값이 작아지는 경우, 감소하는 수라고 한다. 반면 322, 235 등은 위의 정의에서 벗어나기에 감소하는 수가 아니다.

0을 0번째 감소하는 수, 1을 1번째 감소하는 수, 9를 9번째 감소하는 수 라고 했을 때,

주어진 N에 관하여, N번째 감소하는 수의 값을 구하여라

2. 푸는 원리

조합이다. 하지만 원래의 조합처럼 오름차순으로는 풀 수 없다.

(1) 첫번째 자릿수를 고정하고, 그 자릿수를 limit으로 정한다.
(2) 조합을 돌며, 두 번째 자릿수는 limit보다 작은 수 중에서 하나를 택한다.
(3) 재귀를 돈다.
(4) 세 번째 자릿수를 고를 때는 두 번째 자릿수가 넘어설 수 없는 limit이다.
(5-1) 3,4를 현재 구해야하는 자릿수 만큼 돈다.
(5-2) 기저 조건은 다음과 같다. N번째 감소하는 수에 도착하면 해당 수를 출력한다.
만약 1022번째 수를 넘어선다면 -1을 출력한다.

3. 코드 분석

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

/*
* 감소하는 수 - 조합
* (1) 조합으로 구해야하는 값의 자릿수 선정
* (2) 해당 자릿수에서 시작 숫자 선정
* (3) 시작 숫자에서 역순으로 값 구하기
* */

public class Main {

    static int N;

    static StringBuilder sb = new StringBuilder();

    static int [] arr = {0,1,2,3,4,5,6,7,8,9};
    static int [] output;

    static int cnt = 9;

    static boolean isValid = false;

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

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


        // 1. 예외 처리
        if(N >= 0 && N < 10){
            System.out.println(N);
        }


        // 2. 조합으로 값 구하기
        for (int i = 2; i <= 10; i++) {

            // 자릿수 구하기
            output = new int [i];

            // 맨 앞의 수 구하기
            for (int j = 1; j < 10; j++){
                output[0] = j;
                Combination(1,j);
                if(isValid){
                    return;
                }
            }
        }

        // 3. 제한 횟수 내에 못 찾았으면 에러
        if(cnt < N){
            System.out.println(-1);
        }
    }

    // limit을 이전 배열 값으로 정해서 그 이상은 넘지 않도록 한다.
    public static void Combination (int depth,  int limit) {
        // 1) 기저 조건
        if(depth == output.length){

            cnt++;

            if(cnt == N){
                isValid = true;
                for (int temp : output){
                    System.out.print(temp);
                }
            }

            return;
        }

        for (int i = 0; i < limit; i++) {
            output[depth] = i;
            Combination(depth+1, i);
        }
    }
}