글 읽기 - 출력 오류 질문드립니다

Rche 6년 전 0

이항계수 DP로 풀었습니다.

채점중에 자꾸 35초 부근에서 끊기길래 도저히 이해가 안되서 다른 분들 정답소스와 출력비교를 해봤는데(0~1023 까지) 서로 다른 출력도 없다는데...

어디서 버그가 발생하는지 도저히 모르겠습니다.

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

int DP[11][11];
int nCr(int n,int r) {
    int &ret = DP[n][r];
    if(ret != -1) return ret;
    if(r == 0 || n == r) return ret = 1;
    else return ret = nCr(n-1,r-1) + nCr(n-1,r);
}

string make(int sN,int N,int& pN) {
    if(N == 0) {
        return string("");
    }
    int fn = sN-1;
    while(nCr(fn,N) > pN) {
        fn--;
    }
    pN -= nCr(fn,N);
    string ret("");
    char temp = (char)('0'+fn);
    ret.push_back(temp);
    return ret + make(fn,N-1,pN);
}

int main()
{
    for(int i=0; i<=11; i++)
        for(int j=0; j<=11; j++)
            DP[i][j] = -1;
    int N=0;
    string ans;
    cin >> N;
    if(N > 1022) {
        cout << -1 << endl;
        return 0;
    }
    for(int i=1; i<=11; i++) {
        if(nCr(10,i) <= N) N -= nCr(10,i);
        else {
            ans = make(10,i,N);
            break;
        }
    }
    cout << ans;
    return 0;
}

djm03178 6년 전 1

1022를 넣고 nCr 함수의 호출을 추적해봤더니 r > n인 경우들이 있었습니다. dp[-1][0] 등지에 접근하는데 무슨 동작을 일으킬지는 알 수 없네요.

adh0463 6년 전 1

for(int i=1; i<=11; i++) {

if(nCr(10,i) <= N) N -= nCr(10,i);
else {
ans = make(10,i,N);
break;
}
}

for문은 11까지 도는데 nCr은 nCr(10,11)을 호출하게 되는데, 여기가 아닌가 싶어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

출력 오류 질문드립니다

Rche 6년 전 0

djm03178 6년 전 1

adh0463 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말