2016년 4월 5일 화요일

1174 - 줄어드는 수

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

나올 수 있는 가장 큰 값은 9876543210 (10자리) 이다.
1자리 수(0~9)부터 10자리 수에 대해서 각각 감소하는 수를 모두 구하면 된다.
n자리로 이루어진 모든 감소하는 수는 재귀로 구현했다.
유사한 문제
- 1038번: 감소하는 수


#include <bits/stdc++.h>
using namespace std;

string num[10]={"0","1","2","3","4","5","6","7","8","9"};

void make(vector<string>& ret, string s, int d, int pos, int n){
    if(pos >= n){
        ret.push_back(s);
        return;
    }
    
    for(int i=0; i<d; ++i){
        make(ret, s + num[i], i, pos+1, n);
    }
}

int main(){
    int k, K;
    scanf("%d", &K);
    if(K > 1023) return puts("-1"), 0;
    
    vector<string> result;
    for(k=0; k<=K;){
        // 1자리 ~ 10자리
        for(int i=1; i<=10; ++i){
            vector<string> v;
            make(v, "", 10, 0, i);
            for(int j=0; j<v.size(); ++j) result.push_back(v[j]);
            k += v.size();
        }
    }
    puts(result[K-1].c_str());
    return 0;
}
댓글 쓰기

게시글 목록