https://www.acmicpc.net/problem/1174
1174번: 줄어드는 수
음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는
www.acmicpc.net
코드설명
DFS를 활용한 브루트포스(깊이우선탐색, bruteforce) 문제입니다.
문제 이해가 조금 어려운 문제입니다.
N번쨰로 작은 줄어드는 수라는 의미는, 1번쨰로 작은 줄어드는 수를 찾으라는 의미입니다.
방법은 다음과 같습니다.
1. 줄어드는 수를 모두 구합니다.
2. 줄어드는 수를 정렬합니다.
3. N번째 수는 출력합니다.
4. 재귀를 진행하며 숫자를 추가할것인가, 추가하지 않을것인가 하는 2가지의 선택이 존재합니다. 현재 arr에는 9 8 7 6 5 4 3 2 1 0 이라는 10가지 수가 존재합니다. 2는 총 10번 선택할 수 있습니다. 2^10 = 1024 입니다. 만약 N이 1024보다 크거나 같은 수라면 해당 경우는 없습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[][] map;
public static int[] arr = {9,8,7,6,5,4,3,2,1, 0};
public static int cnt = 0;
public static ArrayList<Long> arrList = new ArrayList<Long>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
DFS(0, 0);
Collections.sort(arrList);
if(N <= 1023) {
System.out.println(arrList.get(N-1));
}else {
System.out.println("-1");
}
}
public static void DFS(int level, long num) {
if( arrList.contains(num) == false) {
arrList.add(num);
}
if(level >= 10)
return ;
DFS(level + 1, (num * 10) + arr[level] );
DFS(level + 1, (num) );
}
}