문제
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.
입력
첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 N번째 감소하는 수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<ll> v;
void dfs(ll num) {
v.push_back(num);
for (int i = 0; i < num % 10; i++)
dfs(num * 10 + i);
}
int main() {
int n;
cin >> n;
for (int i = 0; i <= 9; i++)
dfs(i);
sort(v.begin(), v.end());
try {
cout << v.at(n) << '\n';
}
catch (...) {
cout << -1 << '\n';
}
return 0;
}
|
cs |
n이라는 감소하는 숫자가 있다고 하면 n에 n%10보다 작은 수를 붙이면 또 다른 감소하는 수를 만들 수 있다.
그래서 그 숫자들을 전부 벡터에 넣은 뒤 정렬하는 방식으로 해결했다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
백준 온라인 저지 16508 전공책 (1) | 2020.12.24 |
---|---|
백준 4920 테트리스 게임 (0) | 2020.12.14 |
백준 온라인 저지 5958 Space Exploration (0) | 2020.12.07 |
백준 온라인 저지 2676 라스칼 삼각형 (0) | 2020.12.07 |
백준 온라인 저지 1406 에디터 (0) | 2020.12.07 |