[백준] 2407번 : 조합 [C/C++]

#문제

2407번: 조합

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

2407번: 조합

 

---

#접근방법

조합을 구하는 식 (nCm = n-1Cm-1 + n-1Cm)을 이용하고,

 

long long 범위를 벗어나는 조합값이 있으므로 string 자료형으로 큰 수 덧셈으로 조합값을 구하면 된다.

반응형

---

#풀이

#include <iostream>
using namespace std;

string arr[105][105];

string add(string num1, string num2){
    string num = "";
    int sum = 0;
    int size = max(num1.size(),num2.size());

    for(int i=0;i<size || sum;i++){
        if(num1.size()>i) sum += num1[i]-'0';
        if(num2.size()>i) sum += num2[i]-'0';

        num += sum%10 +'0';
        sum /= 10;
    }

    return num;
}

string combi(int n,int m){
    if(n==m || m==0) return "1";

    string &ans = arr[n][m];

    if(ans!="") return ans;

    ans = add(combi(n-1,m-1), combi(n-1,m));

    return ans;
}

int main(){
    int n,m;

    cin >> n >> m;

    combi(n,m);

    for(int i=arr[n][m].size()-1;i>=0;i--)
        cout << arr[n][m][i];

    return 0;
}

long long 값을 벗어나는 조합값이 있으므로 string자료형으로 큰 수 덧셈함수를 만들어서 구하였다.

 

combi함수는 nCm = n-1Cm-1 + n-1Cm 이라는 성질을 이용하여 재귀함수로 만들었고,

 

arr 이차원 배열을 만들어서 한 번 구한 값을 다시 사용할 수 있도록 메모제이션 방법을 이용하여서 속도를 빠르게 하였다.

 

add함수는 string자료형으로 큰 수 덧셈을 하는 함수다.

 

마지막으로 출력할 때, arr 배열에 숫자가 거꾸로 되어 있으므로 뒤에서 부터 출력해주었다.

---

#성능

---

#정리

조합의 성질 nCm = n-1Cm-1 + n-1Cm (nCn = 1, nC0 = 1) 을 알고,

 

string 자료형으로 큰 수 덧셈을 하는 방법과,

 

메모제이션을 사용해 이미 구한 답을 이용하여 속도를 빠르게 하는 방법을 알고 있으면 풀 수 있는 문제였다.