[Gold V] 줄어드는 수 - 1174
성능 요약
메모리: 12972 KB, 시간: 88 ms
분류
백트래킹, 브루트포스 알고리즘
제출 일자
2024년 2월 3일 19:22:01
문제 설명
음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.
N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.
입력
N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 N번째 작은 줄어드는 수를 출력한다.
접근 방법
1. N이 줄어드는 수라면 최대값은 9876543210이다.
2. 즉 10자리까지 줄어드는 수를 구한다. 구하는 과정에 카운트를 하며 N만큼 했다면 출력 후 종료한다.
3. 또한 숫자가 10자리로 간다면 int 범위를 초과하므로 long으로 값을 가진다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
// N번째 수를 받는다.
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
// N이 1023보다 크다면 존재하지않음 -> -1
if(N > 1023){
System.out.println(-1);
return;
}
// 숫자는 1자리부터 10자리까지 구한다. 그 과정에서 값을 도출시 프로그램 종료
for (int i = 1; i <= 10; i++) {
combination(0, 10, 0, i);
}
System.out.println(-1);
}
private static void combination(int depth, int end, long value, int limit) {
// 현재 깊이가 낼 수 있는 자리수에 도달한다면
if (depth == limit) {
// N을 감소
N--;
// N이 0이라면 해당 값을 출력 후 프로그램 종료
if (N == 0) {
System.out.println(value);
System.exit(0);
}
return;
}
// i는 0부터 End까지 진행한다. 다음 end값은 i값을 넘겨주어 0부터 ~ i까지 즉, 더 작은 값만 나오도록 한다.
for (int i = 0; i < end; i++) {
combination(depth + 1, i, value * 10 + i, limit);
}
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 1967번 : 트리의 지름 Gold4(골드4) - JAVA[자바] (1) | 2024.02.09 |
---|---|
[백준] 16637번 : 괄호 추가하기 Gold3(골드3) - JAVA[자바] (0) | 2024.02.05 |
[백준] 17825번 : 주사위 윷놀이 골드2(Gold2) - JAVA[자바] (1) | 2024.02.02 |
[백준] 15684번 : 사다리 조작 Gold3(골드3) - JAVA[자바] (0) | 2024.01.31 |
[백준] 13023번 : ABCDE Gold5(골드5) - JAVA[자바] (1) | 2024.01.29 |