문제
https://www.acmicpc.net/problem/1038
풀이
n번째로 높은 자리에서 낮은 자리로 감소하는 수를 구하는 문제이다.
모든 경우의 수를 따져보면, 총 1023개이다.
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 집합의 부분집합을 구하면 무조건 감소하는 수를 만들 수 있다.
하지만 모두 다 안 고르는 경우
공집합 경우가 있으므로, 총 경우의 수는 1023개이다.
1. 10번째 이하일 때는 n을 그대로 출력한다.
2. 0 ~ 9사이에서 1자리로 시작해서 10을 나머지 연산한 값보다 작은 값들을 계속 일의 자리로 붙여 리스트에 담는다.
10을 나머지 연산하면 일의 자리가 나오고 그 수보다 작은 값을 붙이면 감소하는 수가 되기 때문이다.
9876543210이 최대 자리이기 때문에, 자릿 수가 10보다 크면 재귀를 빠져나온다.
3. 오름차순으로 정렬한다.
4. n이 감소하는 수들의 리스트 수 이상이면 -1을 출력하고 그게 아니라면 감소하는 수를 출력한다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
private static ArrayList<Long> list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
if (n <= 10) {
System.out.print(n);
return;
}
list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
dfs(i, 1);
}
Collections.sort(list);
if (n >= list.size()) {
System.out.print(-1);
return;
}
System.out.print(list.get(n));
br.close();
}
private static void dfs(long num, int depth) {
if (depth > 10) {
return;
}
list.add(num);
for (int i = 0; i < num % 10; i++) {
dfs((num * 10L) + i, depth + 1);
}
}
}
실행결과

'Problem Solving > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 교환 - Java (0) | 2025.08.31 |
|---|---|
| [Problem Solving] 코딩테스트 준비 전략 (0) | 2025.08.25 |
| [Baekjoon] 과일 탕후루 - Java (0) | 2025.08.21 |
| [Baekjoon] 올림픽 - Java (0) | 2025.08.17 |
| [Baekjoon] 백준 12865: 평범한 배낭 - Java (0) | 2025.06.22 |