글 읽기 - 중복조합을 이용하여 풀면 틀리는 이유가 무엇일까요?

kwldjs1023 2년 전 0

무언가 틀린 이유가 있을텐데 잘 모르겠습니다ㅠ

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

int main(){
    int n;
    cin >> n;
    long com[1001] = {-1, 10};
    for(int i=2; i<=n; ++i){
        com[i] = com[i-1]*(9+i)/i;
        com[i]%=10007;
    }
    cout << com[n];
}

frog123 2년 전 2

수식에 나눗셈이 있어서 %=10007한 값과 계산 시 문제가 생기는 것 같네요.

예를 들어, (10,010/2)%10,007 = 5,005입니다.

근데 (10,010%10,007)/2 = 1.5가 됩니다.

실제로 구하고 싶은 값은 (com[1]*10/1*11/2*12/3*...)%10,007 이지만

위 수식에서는 ((com[1]*10/1%10,007)*11/2%10,007)*12/3%10,007로 계산하고 있습니다.

그래서 com[i]값이 10,007을 넘긴 이후부터 이상한 값이 나옵니다.

틀린 부분) 중간중간 %10007을 해 주시면 중간에 실수값이 나오는 경우가 생깁니다. 그렇기에 마지막에 %10007을 해 주어야 합니다. 하지만, 이렇게 한다면 long long의 범위를 중간에 넘어갑니다. long을 사용하셨는데, long long을 사용하는 것이 이롭습니다. long long을 이용하여 풀고 나면 최대 자리 수인 1000을 입력받은 경우를 기준으로, 8번째 계산(*1002/8*1001/9)부터 long long을 넘어간다는 것을 계산해보면 구할 수 있습니다. 그렇기에 7에서 %10007을 하여 숫자를 축소시키고, 그 후 10007을 더해나아가는 값들 중, 72의 배수인 것을 구해야 합니다. 이렇게 하면 답을 구할 수 있습니다. 도움이 되었기를 바랍니다. 중간에 인위적으로 조작하지 않으면 해당 문제는 풀기 어려운 것 같습니다.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
unsigned long long Combination(int a, int b)
{
    unsigned long long i, division=1, result=1, cnt=0, nummod=0, numod=0, k=0; 
    for(i=a;i>a-b;i--)
    {
        if(cnt==7)
        {
            result%=10007;
            numod=(result*i*(i-1))%72;
            nummod=(10007*i*(i-1))%72;
            while((numod+k*nummod)%72!=0)
            {
                k++;
            }
            result+=k*10007;
        }
        result*=i;
        result/=division;
        division++;
        cnt++;
    }
    return(result);
}
int main()
{
    unsigned long long n;
    cin>>n;
    cout<<Combination(10+n-1, 9)%10007;
    return 0;
}

문제

문제

출처

ICPC

중복조합을 이용하여 풀면 틀리는 이유가 무엇일까요?

kwldjs1023 2년 전 0

frog123 2년 전 2

angelsiwoo2 2년 전 2

angelsiwoo2 2년 전 0

angelsiwoo2 2년 전 0

kwldjs1023 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말