MORSE 오답 문의 드려요.

  • jongyeop.lee
    jongyeop.lee

    '오답' 나오는데 이유를 모르겠어요.

    예제도 다 정답이 나오고

    100 100 10 등 큰 값에 대해서도 정답이 나오는데

    이유를 모르겠네요. ㅠㅜ

    도와 주세요 ^^

    #include <iostream>

using namespace std;

double factorial(int n) {
    return (n == 0 || n == 1) ? 1 : n * factorial(n - 1);
}

double comb(int n, int r) {
    return factorial(n) / (factorial(n - r) * factorial(r));
}

void getMorse(int n, int m, unsigned long k, string& code) {
    if (k == 1) {
        while(n--)
            code.push_back('-');

        while(m--)
            code.push_back('o');
        return;
    }

    double num = comb(n + m - 1, m);
    if (num >= k) {
        code.push_back('-');
        return getMorse(n - 1, m, k, code);
    }

    code.push_back('o');
    return getMorse(n, m - 1, k - num, code);
}

int main() {
    int numOfCase;
    cin >> numOfCase;

    while(numOfCase) {
        int n, m;
        unsigned long k;
        cin >> n >> m >> k;

        string code;
        getMorse(n, m, k, code);
        cout << code << endl;

        --numOfCase;
    }

    return 0;
}

    8년 전
3개의 댓글이 있습니다.
  • jongyeop.lee
    jongyeop.lee

    double 의 오차 때문에 발생한 문제네요.
    겨우 겨우 문제 해결했네요.
    return getMorse(n, m - 1, k - num, code);
    => return getMorse(n, m - 1, k - num + 0.5, code);


    8년 전 link
  • jongyeop.lee
    jongyeop.lee

    factorial을 cache에 저장해도 되고 combination 값을 cache에 저장해서 해결되도 됩니다.
    감사합니다.


    8년 전 link
  • joowon
    joowon

    double에서 왜 오차가 생기는지 설명해 주실 수 있으신가요?? ㅠㅠ
    저는 unsigned형만 썼는데 비슷한 상황이네요


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.