글 읽기 - 조언 부탁드립니다.. 조합으로 오버플로우 나지 않도록 해봤습니다.

behappyis 5년 전 0

항상 감사드립니다.

지적 부탁드립니다.. 조합으로 오버플로우 나지 않도록 해봤습니다.

예제와 질문에 있는 많은 테스트케이스를 해봤는데..문제없어서 제출했습니다만 바로 틀려버리네요.

좋은 하루되셨기를 바랍니다.

(해결함)

매번 나누기에 정확히 나누어 떨어지지 않는 경우의 오차

그리고 29개중에 14,15,16개를 선택하는 경우의 오버플로어의 문제가 발생했습니다.

규칙을 발견해 1-29중에 1-29를 선택하는 경우를 미리 계산해놓고 푸는 방식으로 해결했습니다.

#include <iostream>
using namespace std;
int main(void)
{
    int T;
    cin >> T;
    
    int r,n;
    int k,l;
    unsigned long long int result;
    
    for(int i=0;i<T;i++)
    {
        
        cin >> r >> n;
        
        result=1;
        
        k=r;
        l=n-r;
        
        //n!/(r!*(n-r)!)
        for(int j=n;j>0;j--)
        {
            result*=j;
            if(k==j)
            {
                result/=k;
                k--;
            }
            if(l==j)
            {
                result/=l;
                l--;
            }
        }

        cout << result << endl;
    }
    
    return 0;
}

jaehoo1 5년 전 0

15 30

behappyis 5년 전 0

조언감사드립니다.

그런데 조건이

0 < N ≤ M < 30

이라 30은 입력이 안나올것 같습니다.

감사합니다.

behappyis 5년 전 0

감사드립니다.

실제 조합의 값을 확인해보니

14 29

15 29

등이 다른 값이 나오는것을 확인했습니다.

다시 연구를 해보겠습니다.

jaehoo1 5년 전 0

아 그러네요 죄송합니다

≤ 인줄 알았네요

여튼 nCr의 값이 오버플로나는 경우를 말하려고 한거였습니다

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

문제

문제

출처

ICPC

조언 부탁드립니다.. 조합으로 오버플로우 나지 않도록 해봤습니다.

behappyis 5년 전 0

jaehoo1 5년 전 0

behappyis 5년 전 0

behappyis 5년 전 0

jaehoo1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말