[BOJ/C++] 2407: 조합

다곰·2023년 3월 24일
0

우당탕탕 코테준비

목록 보기
46/98

🥈 Silver 1

✏️ 솔루션

⭐️ 파스칼의 삼각형 사용해서 조합 계산하기
⭐️ 숫자가 커지기 때문에 숫자형이 아닌 문자열로 저장하기

  • calc 함수: nCm = n-1Cm-1 + n-1Cm 구하기
    ❗️ 두 수 자릿수가 다르면 큰 수가 a
    1) 일의 자리수부터 b의 자리수를 a에 더하기 ➡️ 만약 10을 넘기면 올림수를 저장해두고 현재 a 자리에는 일의 자리수 넣기
    2) 현재가 a 의 가장 큰 자리수라면 현재까지 갱신한 a 앞에 1 붙여서 올림수까지 반영해주기
    3) b 를 모두 반영했으나 올림수가 남아있으면 올림수가 남지 않을 때까지 모두 반영해주기
    4) 올림수가 계속해서 발생하려면 현재 a의 자리수가 9 여야 하기 때문에 9이면 현재 자리수를 0으로 바꾸기
    ❗️ a 의 가장 큰 자리수까지 반영했는데도 올림수가 남아있으면 현재까지 갱신한 a 앞에 1 붙여서 올림수까지 반영해주기

✏️ code

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

string comb[101][101];

string calc(string a, string b) {
    int up=0;
    for(int i=1;i<=a.size();i++) {
        if (i>b.size()) {
            if(up==0) break;
            else if(a[a.size()-i]<'9') {
                a[a.size()-i]+=1;
                up=0;
            }
            else {
                a[a.size()-i]='0';
                if(i==a.size()) return "1"+a;
            }

            continue;
        }
        
        int k = a[a.size()-i]-'0'+b[b.size()-i]-'0'+up;
        up=0;
        if(k<10) a[a.size()-i]=k+'0';
        else {
            up=1;
            a[a.size()-i]=(k%10)+'0';
            if(i==a.size()) return "1"+a;

        }
        
    }
    return a;
}

int main() {
    
    comb[5][0]=comb[5][5]="1";
    comb[5][1]=comb[5][4]="5";
    comb[5][2]=comb[5][3]="10";

    for(int i=6;i<=100;i++) {
        for(int j=0;j<=i;j++) {
            if(j==0 || j==i) comb[i][j]="1";
            else {
                string a=comb[i-1][j-1];
                string b=comb[i-1][j];

                if (a.size()>=b.size()) comb[i][j]=calc(a, b);
                else comb[i][j]=calc(b, a);

            }
        }
    }
    
    int n,m;
    cin >> n >> m;
    cout << comb[n][m];
    
}
profile
다교미의 불꽃 에러 정복기

0개의 댓글