[백준 알고리즘] 1174번 : 줄어드는 수 (JAVA) 문제 풀이

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

 

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

1174번: 줄어드는 수

 

문제풀이 : 

처음에 N이 의미하는 바가 무슨 말인지를 이해하지 못해서 한참 걸렸다.. (바보..)

N번째 작은 줄어드는 수를 출력하라는 말은 즉, 줄어드는 수에 해당하는 수들을 쭈욱 일렬로 세워두었을 때, 그중 N번째로 작은 줄어드는 수를 출력하란 뜻이다.

(문제 겁나 어렵네 진짜)

 

자 나는 그리하여, 우선은 모든 수 중에 줄어드는 수가 가장 큰 것은 무엇일까?

9876543210이다.

 

자 그렇다면, 이 문제를 풀기위해서 어떠한 알고리즘을 이용해야 할까?

우선 줄어드는 수 모두를 탐색하는 것이 좋다. (브루트 포스 알고리즘)

단, 모든 수중에 줄어드는 수 그리고 또한 N번째 수를 찾는 것이다. (백트래킹)

 

이 2가지의 알고리즘을 이용하는 것이다.

 

List안에 모든 줄어드는 수를 집어 넣은 뒤에 정렬시켜서 N을 통해서 해당 값을 찾으면 된다.

 

내 코드 : 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
// 백준알고리즘 1174번 줄어드는수

public class Main {

	static int N;
	static int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	static List<Long> list = new ArrayList<>();

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();

		DFS(0, 0);
		list.sort(null);

		try {
			System.out.println(list.get(N - 1));
		} catch (Exception e) {
			System.out.println(-1);
		}

	}

	public static void DFS(long num, int inx) {
		if (!list.contains(num)) {
			list.add(num);
		}

		if (inx >= 10) {
			return;
		}

		DFS((num * 10 + arr[inx]), inx + 1);
		DFS(num, inx + 1);
	}
}

https://dingdingmin-back-end-developer.tistory.com/entry/%EB%B0%B1%EC%A4%80-1174%EC%9E%90%EB%B0%94-java-%EC%A4%84%EC%96%B4%EB%93%9C%EB%8A%94-%EC%88%98

백준 1174[자바] java 줄어드는 수

 

해당 블로그를 참고하여 문제를 풀었습니다.