글 읽기 - 케이스 질문드려요

leechhe 8년 전 0

코드는 재귀적으로 감소하는 수를 찾아나가도록 했습니다. comb는 10Cn의 값을 저장한 배열입니다. 일단 n에 따라 자릿수의 길이를 구하고

해당 길이의 감소하는 수가 나올 때까지 하나씩 세나가는 방식입니다.

재귀함수가 return할 때(n < 0 ) 가장 끝자리부터 스택에 넣고 이 후 출력합니다.

0부터 n의 결과값이 -1이 될 때까지 출력해봤는데... 문제 없이 잘 나오는 거 같은데ㅠㅠㅠ 틀린 부분 알려주시면 감사하겠습니다.

#include <cstdio>
#include <stack>
using namespace std;
char num[11] = "9876543210";
int n;
stack<char> s;
void dfs(int cur, int step){
    if( step == 1 ){
        --n;
        if( n < 0 ){
            s.push(num[cur]);
        }
        return;
    }
    for( int i = 11-step; i > cur ; --i ){
        dfs(i, step-1);
        if( n < 0 ){
            s.push(num[cur]);
            return;
        }
    }
}
int main(){
    int comb[9] = { 10, 45, 120, 210, 252, 210, 120, 45, 10 };
    scanf("%d",&n);
    for( int i = 0 ; i < 10 ; ++i ){
        if( n - comb[i] < 0 ){
            int len = i+1;
            for(int j = 10-len ; j >= 0 ; --j ){
                dfs(j, len);
                if(!s.empty()) break;
            }
            if(!s.empty()) break;
        }
        n -= comb[i];
    }
    if( s.empty() ) printf("-1");
    else{
        while(!s.empty()){
            printf("%c",s.top());
            s.pop();
        }
    }
    return 0;
}