https://www.acmicpc.net/problem/1834
문제
> 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다.
> 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.
> N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오.
> 만약 그러한 수가 없을 때는 -1을 출력한다.
> 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.접근
백트래킹을 이용하여 가능한 모든 수를 만든다.
0부터 시작해서 9까지 보는데 한자리수 일땐 0부터 9까지 모두 가능하고 두 자리 수 일땐, 10, 20, 21, 30, 31, 32, 40,41,42,43...으로 앞자리 수 보다 작은 수까지만 올 수 있다. 이를 재귀로 하면 반복문에서 현재의 i값을 다음 재귀의 반복문의 최대값으로 넘겨주는 걸로 구할 수 있다.
다 구하고 나면 모든 수를 저장하고 N번째를 따져줘야하므로 오름차순으로 정렬해준다. 이 중 N번째를 찾으면 되고, N이 이 수들의 총 개수보다 크면 -1을 출력한다.
문제해결
> 문제에서 정수라고 주어졌는데 N에 대한 범위는 있지만 가능한 줄어드는 수 의 범위가 없으므로 정수의 가장 큰 long long형으로 잡는다.
> 재귀함수 Decnum에서 파라미터로 줄어드는 수인 num과 반복문의 최대값인 idx를 받는다.
> main문에서 처음에 0, 10이 들어가므로 0부터 시작해서 10보다 작은 수 까지 반복문을 돌게된다.
> 첫Decnum에선 0*10+0, 0*10+1, 0*10+2...로 한자리수가 만들어지고 decnum벡터에 저장된다.
> 저장된 후 재귀로 해당 수와 i를 가지고 재귀로 들어간다.
> 만약 tmp가 3, i가 3이면 0부터 3보다 작을 때 까지 3*10+0, 3*10+1, 3*10+2까지 만들어지고 저장된다.
> 재귀가 깨지는건 반복문이 돌아가지 못하는 경우에 자동으로 깨지게 되어있다.
> 이제 모든 경우를 구했으면 decnum벡터를 정렬해주고 N이 벡터의 크기보다 큰지 확인한다.
> 크면 불가능하므로 -1출력하고 아니면 N-1을 인덱스로 가지는 수를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
vector<long long> decnum;
void Decnum(long long num, int idx)
{
for (int i = 0; i < idx; i++)
{
long long tmp = num * 10 + i;
decnum.push_back(tmp);
Decnum(tmp, i);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
Decnum(0, 10);
sort(decnum.begin(), decnum.end());
if (N > decnum.size())
{
cout << -1 << '\n';
return 0;
}
cout << decnum[N - 1] << '\n';
}
후기
총 몇개의 수가 나오게 될지 몰라서 정렬을 쓸까말까 했는데 총 개수가 1000몇개 정도 나온다고 하므로 맞췄다.
