[BOJ 1038] 감소하는 수

문제 링크 : https://www.acmicpc.net/problem/1038

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

제한

시간 제한	메모리 제한
1sec	512MB

---

풀이

처음에는 $N$이 생각보다 커서 구하려는 수가 오버플로가 날 것 이라고 생각했는데, 잘 생각해보면 그렇지 않다는 것을 알 수 있다. 문제의 조건에서 “감소하는 수”는 그 자릿수가 매번 작아져야한다. 그러기 위해서는 맨 앞자리가 $9$이더라도 뒷자리로 갈 때마다 최소 $1$ 이상은 작아져야하며, 결과적으로 수의 길이는 최대 $10$자리까지 가능하다. 이 상태라면 long long으로 충분히 커버된다.

그럼 만들 수 있는 “감소하는 수”의 개수는 몇개일까? 정답은 대충 $2^{10}$개 정도이다. 감소하는 수 특성상 똑같은 자릿수는 존재할 수 없다. 또한 선택된 자릿수에 대해 감소하는 수 형태는 1개로 고정된다. 그러므로 우리는 $0$부터 $9$까지 가능한 선택지 중 수를 선택하거나 하지 않거나의 개수를 세는 방식으로 감소하는 수의 개수를 셀 수 있다. 여기서 $0$만 선택하는 경우는 $0$번째 감소하는 수이므로, 총 $1\,023$개의 감소하는 수가 존재한다.

그럼 생각보다 찾아야하는 수가 몇 개 없으므로, 그냥 백트래킹 알고리즘으로 모든 수를 찾아보면 될 것 같다. 수를 세는 방법은 (i) 수의 길이 (ii) 가장 앞자리 숫자 이므로, BFS 탐색을 활용한 백트래킹 방식을 채용하여 문제를 해결하자. 찾은 감소하는 수를 배열에 넣고, 배열 안에 있는 index라면 그 수를 출력, 없다면 NONE을 출력하도록 구현하면 된다.

소스코드

Github Link : Source Code

참고 알고리즘 : 백트래킹 알고리즘