[JAVA] 백준 1038 감소하는 수

 

https://www.acmicpc.net/problem/1038

 

문제분석

브루트포스 문제이다. 감소하는 수 List를 만든 뒤, 조회하면 끝이다.

당연히 문제는 "감소하는 수 List만들기" 에 있다.

재귀를 활용한다.

맨 앞의 수가 3인 경우에는, 321가 최대고, 6인 경우는 654321이 최대일 것이다. 물론 654320도 가능하고 654210도 가능하다.

하지만 맨 앞의 수가 3이면서 1자릿수라면 3, 끝이다. 2자릿수라면? 31, 32 2가지 상황이 가능하다.

그렇다면, 재귀를 통해서 1자릿수가 더해진다면 맨 앞의 수를 1칸 왼쪽(곱하기 10)이동 시킨 뒤, 그 아래에 숫자를 넣는다. 넣는 숫자는 당연히 앞의 수보다 크지 않은 모든 수가 가능할 것이다. 따라서 재귀함수에 digit을 넣어줄 필요는 없지만(parsing하면 되기 때문), 편의를 위해 넣었다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static ArrayList<Long> ar;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ar = new ArrayList<>();
        for (int i = 0; i <= 9; i++) recursive(i, i);
        Collections.sort(ar);
        if(N >= ar.size()) System.out.println(-1);
        else System.out.println(ar.get(N));
    }

    public static void recursive(long num, int digit){// digit = 다음에 붙일 수 있는 숫자 상한
        ar.add(num);
        for(int next = 0; next < digit; next++){
            recursive(num * 10 + next, next);
        }
    }
}