[BaekJoon] 1174 줄어드는 수

1.  문제 링크

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

2.  문제

요약

• 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소하는 수를 줄어드는 수라고 합니다.
• N번째로 작은 줄어드는 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1,000,000보다 작거나 같은 자연수인 N이 주어집니다.
• 출력: 첫 번째 줄에 N번째로 작은 줄어드는 수를 출력합니다. 만약 그러한 수가 없다면 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {
	static int[] nums = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
	static ArrayList<Long> arr = new ArrayList<Long>();
	static int num;
	public void dfs(long sum, int index) {
		if(!arr.contains(sum)) {
			arr.add(sum);
		}
		if(index >= 10) {
			return;
		}
		dfs(sum * 10 + nums[index], index + 1);
		dfs(sum, index + 1);
	}
	
	public long getDecreasingNum() {
		dfs(0, 0);
		Collections.sort(arr);
		if(num > 1023) {
			return -1;
		} else {
			return arr.get(num - 1);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		num = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getDecreasingNum() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 줄어드는 수를 만들어야 하는데 0부터 9까지 내림차순으로 정렬된 배열을 이용하여 수를 만든다면 해당 수가 줄어드는 수인지 확인하지 않아도 되기 때문에 이러한 배열을 이용합니다.
• 줄어드는 수를 만들 때는 내림차순으로 정렬된 배열을 이용하여 DFS를 활용해 만듭니다.
• 해당 배열에서 현재 위치에 있는 수를 선택할지 말지를 결정하고 만약 현재 위치에 있는 수를 선택한다면 자리수를 하나 밀어주어 마지막 자리수에 선택한 수를 더해줍니다.
• 만약 선택하지 않는다면 배열의 다음 수에 대해 선택할지 말지를 결정합니다.

public void dfs(long sum, int index) {
	if(!arr.contains(sum)) {
		arr.add(sum);
	}
	if(index >= 10) {
		return;
	}
	dfs(sum * 10 + nums[index], index + 1);
	dfs(sum, index + 1);
}

• 줄어드는 수를 만들 때, 해당 배열의 순서대로 그 수를 선택할지 말지를 결정하는 것이기 때문에 10개의 수에 대해서 선택을 진행하므로 $2^{10}$ = 1024가 줄어드는 수를 만들 때의 경우의 수가 됩니다.
• 그렇기 때문에 1024가 넘는 수에 대해서는 줄어드는 수가 존재하지 않으므로 -1을 출력합니다.

1. 줄어드는 수들을 담을 ArrayList 변수 arr를 하나 생성하고 0부터 9까지 내림차순으로 정렬되어있는 배열인 변수 nums를 생성합니다.
2. DFS를 통해 1024개의 줄어드는 수를 구합니다.
   1. 만약 인자로 넘어온 수 sum이 줄어드는 수들을 담은 arr에 포함되어있지 않다면 해당 수를 arr에 추가합니다.
   2. 만약 인자로 넘어온 배열의 index를 나타내는 index의 값이 10보다 크거나 같다면 배열의 모든 값을 탐색한 것이므로 재귀함수의 호출을 끝냅니다.
   3. 현재 위치의 배열의 수를 선택하는 경우와 선택하지 않는 경우 2가지에 대해서 구해야하므로 아래와 같이 2번의 재귀함수 호출을 진행합니다.

      1. 선택하는 경우

         • sum의 값에 10을 곱하여 자리수를 하나 밀어준 수에 선택한 값을 더하여 새로 만들어진 수와 배열에서 다음 위치를 탐색해야하므로 index 값에 1을 더해줘 재귀함수를 호출합니다.

      2. 선택하지 않는 경우

         • sum의 값은 그대로 전달해주고 배열에서 다음 위치를 탐색해야하므로 index 값에 1을 더해줘 재귀함수를 호출합니다.
3. 구한 줄어드는 수들을 오름차순으로 정렬합니다.
4. 만약 입력으로 주어진 수가 1023을 넘는다면 줄어드는 수의 개수인 1024개보다 크므로 -1을 출력합니다.
5. 그렇지 않다면 입력으로 주어진 수의 위치에 해당하는 arr의 값을 출력합니다.