https://www.acmicpc.net/problem/2407

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net

 

이 문제는 100 C 50 조합 값이 long long int 를 벗어나는 약 30자리 수 정도이기 때문에, 다른 방법으로 덧셈을 계산해야 한다. 따라서 덧셈을 위해 string 클래스를 이용해 문자열끼리의 더하기를 구현하였다.

 

다음은 100_C_n 의 조합의 결과 : 

(100C1) : 1 + 99 = 100
(100C2) : 99 + 4851 = 4950
(100C3) : 4851 + 156849 = 161700
(100C4) : 156849 + 3764376 = 3921225
(100C5) : 3764376 + 71523144 = 75287520
(100C6) : 71523144 + 1120529256 = 1192052400
(100C7) : 1120529256 + 14887031544 = 16007560800
(100C8) : 14887031544 + 171200862756 = 186087894300
(100C9) : 171200862756 + 1731030945644 = 1902231808400
(100C10) : 1731030945644 + 15579278510796 = 17310309456440
(100C11) : 15579278510796 + 126050526132804 = 141629804643600
(100C12) : 126050526132804 + 924370524973896 = 1050421051106700
(100C13) : 924370524973896 + 6186171974825304 = 7110542499799200
(100C14) : 6186171974825304 + 38000770702498296 = 44186942677323600
(100C15) : 38000770702498296 + 215337700647490344 = 253338471349988640
(100C16) : 215337700647490344 + 1130522928399324306 = 1345860629046814650
(100C17) : 1130522928399324306 + 5519611944537877494 = 6650134872937201800
(100C18) : 5519611944537877494 + 25144898858450330806 = 30664510802988208300
(100C19) : 25144898858450330806 + 107196674080761936594 = 132341572939212267400
(100C20) : 107196674080761936594 + 428786696323047746376 = 535983370403809682970
(100C21) : 428786696323047746376 + 1613054714739084379224 = 2041841411062132125600
(100C22) : 1613054714739084379224 + 5719012170438571889976 = 7332066885177656269200
(100C23) : 5719012170438571889976 + 19146258135816088501224 = 24865270306254660391200
(100C24) : 19146258135816088501224 + 60629817430084280253876 = 79776075565900368755100
(100C25) : 60629817430084280253876 + 181889452290252840761628 = 242519269720337121015504
(100C26) : 181889452290252840761628 + 517685364210719623706172 = 699574816500972464467800
(100C27) : 517685364210719623706172 + 1399667836569723427057428 = 1917353200780443050763600
(100C28) : 1399667836569723427057428 + 3599145865465003098147672 = 4998813702034726525205100
(100C29) : 3599145865465003098147672 + 8811701946483283447189128 = 12410847811948286545336800
(100C30) : 8811701946483283447189128 + 20560637875127661376774632 = 29372339821610944823963760
(100C31) : 20560637875127661376774632 + 45764000431735762419272568 = 66324638306863423796047200
(100C32) : 45764000431735762419272568 + 97248500917438495140954207 = 143012501349174257560226775
(100C33) : 97248500917438495140954207 + 197443926105102399225573693 = 294692427022540894366527900
(100C34) : 197443926105102399225573693 + 383273503615787010261407757 = 580717429720889409486981450
(100C35) : 383273503615787010261407757 + 711793649572175876199757263 = 1095067153187962886461165020
(100C36) : 711793649572175876199757263 + 1265410932572757113244012912 = 1977204582144932989443770175
(100C37) : 1265410932572757113244012912 + 2154618614921181030658724688 = 3420029547493938143902737600
(100C38) : 2154618614921181030658724688 + 3515430371713505892127392912 = 5670048986634686922786117600
(100C39) : 3515430371713505892127392912 + 5498493658321124600506947888 = 9013924030034630492634340800
(100C40) : 5498493658321124600506947888 + 8247740487481686900760421832 = 13746234145802811501267369720
(100C41) : 8247740487481686900760421832 + 11868699725888281149874753368 = 20116440213369968050635175200
(100C42) : 11868699725888281149874753368 + 16390109145274293016493707032 = 28258808871162574166368460400
(100C43) : 16390109145274293016493707032 + 21726423750712434928840495368 = 38116532895986727945334202400
(100C44) : 21726423750712434928840495368 + 27651812046361280818524266832 = 49378235797073715747364762200
(100C45) : 27651812046361280818524266832 + 33796659167774898778196326128 = 61448471214136179596720592960
(100C46) : 33796659167774898778196326128 + 39674339023040098565708730672 = 73470998190814997343905056800
(100C47) : 39674339023040098565708730672 + 44739148260023940935799206928 = 84413487283064039501507937600
(100C48) : 44739148260023940935799206928 + 48467410615025936013782474172 = 93206558875049876949581681100
(100C49) : 48467410615025936013782474172 + 50445672272782096667406248628 = 98913082887808032681188722800
(100C50) : 50445672272782096667406248628 + 50445672272782096667406248628 = 100891344545564193334812497256
(100C51) : 50445672272782096667406248628 + 48467410615025936013782474172 = 98913082887808032681188722800
(100C52) : 48467410615025936013782474172 + 44739148260023940935799206928 = 93206558875049876949581681100
(100C53) : 44739148260023940935799206928 + 39674339023040098565708730672 = 84413487283064039501507937600
(100C54) : 39674339023040098565708730672 + 33796659167774898778196326128 = 73470998190814997343905056800
(100C55) : 33796659167774898778196326128 + 27651812046361280818524266832 = 61448471214136179596720592960
(100C56) : 27651812046361280818524266832 + 21726423750712434928840495368 = 49378235797073715747364762200
(100C57) : 21726423750712434928840495368 + 16390109145274293016493707032 = 38116532895986727945334202400
(100C58) : 16390109145274293016493707032 + 11868699725888281149874753368 = 28258808871162574166368460400
(100C59) : 11868699725888281149874753368 + 8247740487481686900760421832 = 20116440213369968050635175200
(100C60) : 8247740487481686900760421832 + 5498493658321124600506947888 = 13746234145802811501267369720
(100C61) : 5498493658321124600506947888 + 3515430371713505892127392912 = 9013924030034630492634340800
(100C62) : 3515430371713505892127392912 + 2154618614921181030658724688 = 5670048986634686922786117600
(100C63) : 2154618614921181030658724688 + 1265410932572757113244012912 = 3420029547493938143902737600
(100C64) : 1265410932572757113244012912 + 711793649572175876199757263 = 1977204582144932989443770175
(100C65) : 711793649572175876199757263 + 383273503615787010261407757 = 1095067153187962886461165020
(100C66) : 383273503615787010261407757 + 197443926105102399225573693 = 580717429720889409486981450
(100C67) : 197443926105102399225573693 + 97248500917438495140954207 = 294692427022540894366527900
(100C68) : 97248500917438495140954207 + 45764000431735762419272568 = 143012501349174257560226775
(100C69) : 45764000431735762419272568 + 20560637875127661376774632 = 66324638306863423796047200
(100C70) : 20560637875127661376774632 + 8811701946483283447189128 = 29372339821610944823963760
(100C71) : 8811701946483283447189128 + 3599145865465003098147672 = 12410847811948286545336800
(100C72) : 3599145865465003098147672 + 1399667836569723427057428 = 4998813702034726525205100
(100C73) : 1399667836569723427057428 + 517685364210719623706172 = 1917353200780443050763600
(100C74) : 517685364210719623706172 + 181889452290252840761628 = 699574816500972464467800
(100C75) : 181889452290252840761628 + 60629817430084280253876 = 242519269720337121015504
(100C76) : 60629817430084280253876 + 19146258135816088501224 = 79776075565900368755100
(100C77) : 19146258135816088501224 + 5719012170438571889976 = 24865270306254660391200
(100C78) : 5719012170438571889976 + 1613054714739084379224 = 7332066885177656269200
(100C79) : 1613054714739084379224 + 428786696323047746376 = 2041841411062132125600
(100C80) : 428786696323047746376 + 107196674080761936594 = 535983370403809682970
(100C81) : 107196674080761936594 + 25144898858450330806 = 132341572939212267400
(100C82) : 25144898858450330806 + 5519611944537877494 = 30664510802988208300
(100C83) : 5519611944537877494 + 1130522928399324306 = 6650134872937201800
(100C84) : 1130522928399324306 + 215337700647490344 = 1345860629046814650
(100C85) : 215337700647490344 + 38000770702498296 = 253338471349988640
(100C86) : 38000770702498296 + 6186171974825304 = 44186942677323600
(100C87) : 6186171974825304 + 924370524973896 = 7110542499799200
(100C88) : 924370524973896 + 126050526132804 = 1050421051106700
(100C89) : 126050526132804 + 15579278510796 = 141629804643600
(100C90) : 15579278510796 + 1731030945644 = 17310309456440
(100C91) : 1731030945644 + 171200862756 = 1902231808400
(100C92) : 171200862756 + 14887031544 = 186087894300
(100C93) : 14887031544 + 1120529256 = 16007560800
(100C94) : 1120529256 + 71523144 = 1192052400
(100C95) : 71523144 + 3764376 = 75287520
(100C96) : 3764376 + 156849 = 3921225
(100C97) : 156849 + 4851 = 161700
(100C98) : 4851 + 99 = 4950
(100C99) : 99 + 1 = 100

 

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;
int n,m;
vector< string > dp[101];
 
string s_add(string s1, string s2){
    string ret = "";
 
    int s1len = s1.length()-1, s2len = s2.length()-1;
    int is_carry = 0;
    while( s1len >= 0 || s2len >= 0){
        int s = ( s1len >= 0 ? s1[s1len]-'0' : 0 ) + ( s2len >= 0 ? s2[s2len]-'0' : 0+ is_carry;
        is_carry = s / 10;
        s %= 10;
 
        ret = (char)(s+'0'+ ret;
        s1len--, s2len--;
    }
    if(is_carry){
        ret = (char)('0'+is_carry) + ret;
    }
    return ret;
}
 
int main(){
    scanf("%d %d",&n,&m);
    
    for(int i=1; i<=n; i++){
        dp[i].resize(n+1);
        for(int j=1;j<n;j++){
            dp[i][j] = "0";
        }
        dp[i][0= dp[i][i] = "1";
    }
    for(int i=2; i<= n; i++){
        for(int j=1; j < i; j++){
            dp[i][j] = s_add(dp[i-1][j-1], dp[i-1][j]);
            // printf("(%dC%d) : %s + %s = %s\n", i,j, dp[i-1][j-1].c_str(), dp[i-1][j].c_str(), dp[i][j].c_str());
        }
    }
    printf("%s\n", dp[n][m].c_str());
    return 0;
}
cs

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03
BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02
BOJ 4811 알약  (0) 2020.08.28

+ Recent posts