[ BOJ / C++ ] 1038번 감소하는 수
이번 문제는 백트레킹을 활용하는 문제였다. 처음에 고민했던 것은 결과값을 n을 입력 받은 후에 구할지, 미리 결과값을 배열로 저장해둘지 결정하는 것이었다. 본인은 결과값들을 배열에 저장하기로 하였다.
우선 조건으로 명시되어야 하는 것이 앞의 자리가 가장 커야한다는 것이었고, 그 다음 자리 수들은 각자의 앞의 자리보다 작아야한다는 것이었다. 이 값들을 검증하고 넣기 위해 result를 vector로 만들었다.
- DFS함수의 인자로
idx
,cnt
를 둔다.idx
는 result vector에 들어가게 될 값이 되고,cnt
는 한번의 사이클동안 result vector에 들어가는 수들을 세는 값이 된다. - DFS함수 안에서 cnt가 10보다 커지면 return을 해준다. 이는 result vector에 9,876,543,210이 들어갈 때만 해당된다.
- i를 0부터 9까지의 범위로 for문을 돌리며 idx%10이 i보다 큰 경우에만
idx*10+i
,cnt+1
의 인자가 들어간 DFS함수를 재귀 호출 해준다. - for문이 끝까지 돌아가고 난 뒤에 return을 해준다.
- 이 DFS함수의
idx
를 0부터 9까지 넣고 반복하면 result vector가 완성된다. - 완성된 result vector는 순서가 뒤죽박죽이므로 sort함수를 사용해 오름차순 정렬해준다.
- 입력된 n이 result vector의 크기보다 크다면 이는 범위를 벗어나므로 -1을 출력해준다.
- 그 외의 경우에는 result[n]을 출력해준다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<long long> result;
void Input(){
cin>>n;
}
void DFS(long long idx, int cnt){
if(cnt>10)
return;
result.push_back(idx);
for(int i=0; i<10; i++){
if(idx%10>i){
DFS(idx*10+i, cnt+1);
}
}
return;
}
void Solution(){
for(int i=0; i<10; i++){
DFS(i, 1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
sort(result.begin(), result.end());
if(result.size()<=n){
cout<<"-1"<<endl;
}
else if(result.size()>n) {
cout<<result[n]<<endl;
}
return 0;
}
Author And Source
이 문제에 관하여([ BOJ / C++ ] 1038번 감소하는 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-C-1038번-감소하는-수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)