
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);
}
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1987 알파벳 (0) | 2026.02.16 |
|---|---|
| [JAVA] 백준 1107 리모컨 (0) | 2026.02.15 |
| [JAVA] 백준 1025 제곱수 찾기 (0) | 2026.02.14 |
| [JAVA] 백준 1022 소용돌이 예쁘게 출력하기 (0) | 2026.02.13 |
| [JAVA] 백준 1360 되돌리기 (0) | 2026.02.12 |