[JAVA] 백준 1038

 

 

1038번: 감소하는 수

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다.

N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

풀이

일반적인 백트래킹 탐색과는 다른 느낌이라서 해결하지 못했고 해답을 찾아보고 이해한 내용을 바탕으로 작성했다.

백트래킹 보다는 그냥 조건에 맞게 탐색하는 느낌이 강했다.

• 백트래킹이 아닌가?

📌 10보다 작은 수

if(N <= 10){
    System.out.println(N);
    return ;
}

10보다 작거나 같은 수들은 모두 감소하는 수이기 때문에 1은 1번째, 10은 10번째가 된다. 그래서 바로 출력해주고 종료해주었다.

📌 모든 값들을 찾고 난 후 값을 담아둔 리스트의 크기보다 큰 수

if(A.size() < N){
    System.out.println("-1");
    return;
}

이 경우의 N번째 수들은 가장 큰 감소하는 수인 9876543210의 순서보다 큰 수이기 때문에 존재하지 않는다.

따라서 -1을 출력해준다.

📌 감소하는 수 탐색

public static void search(long value, int th){
    if(th > 10) return ;

    A.add(value);
    for(int i=0; i<value%10; i++){
        search(value*10 + i, th+1);
    }

}

매개변수로는 현재 값과 현재 총 자릿수를 의미한다. (value는 현재값, th는 자릿수)

• 만약 자릿수가 10보다 커지면 가장 큰 감소하는 수보다 커지기 때문에 종료한다.

value % 10보다 작은 수까지 반복하는데 이는 현재 값에서 다음 값에 올 수 있는 수가 어디까지인지 찾는다.

• 21 다음에 올 수 있는 수는 0밖에 없다.
• 94 다음에 올 수 있는 수는 0, 1, 2, 3이 있다.

재귀로 다음 수를 탐색하는데 현재 값의 자리수를 늘리고 i값을 더해 모든 경우를 탐색해준다.

📌 전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Main {
    static int N;
    static List<Long> A = new ArrayList<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        if(N <= 10){
            System.out.println(N);
            return ;
        }

        for(int i=1; i<10; i++){
            search(i, 1);
        }
        if(A.size() < N){
            System.out.println("-1");
            return;
        }

        Collections.sort(A);
        System.out.println(A.get(N-1));

    }

    public static void search(long value, int th){
        if(th > 10) return ;

        A.add(value);
        for(int i=0; i<value%10; i++){
            search(value*10 + i, th+1);
        }

    }

}

결과