[백준(BOJ)] 2407번 : 조합 - C++[CPP]

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

2407번: 조합

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론
• 임의 정밀도 / 큰 수 연산

 

---

 

⊙ 문제 접근 과정

 

오버플로우를 피하기 위해서 string으로 값을 받아줘야 한다!

1의 자리부터 string에 값을 순서대로 추가해준다.

그리고 reverse로 뒤집어주자!

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
#define MAX 101

int N, M;
string factorial[MAX][MAX];

string bigNumAdd(string n1, string n2) {
    int sum = 0;
    string result;

    //1의 자리부터 더하기
    while (!n1.empty() || !n2.empty() || sum) {
        if (!n1.empty()) {
            sum += n1.back() - '0';
            n1.pop_back();
        }
        if (!n2.empty()) {
            sum += n2.back() - '0';
            n2.pop_back();
        }
        result.push_back((sum % 10) + '0');
        sum /= 10;
    }
    //역순이므로 다시 역순
    reverse(result.begin(), result.end());
    return result;
}

string combination(int n, int r) {
    if (n==r || r==0)
        return "1";
    string &result = factorial[n][r]; // 참조형 변수

    //memoization
    if (result != "")
        return result;

    //파스칼삼각형
    result = bigNumAdd(combination(n-1, r-1), combination(n-1, r));
    return result;
}

int main() {
    cin >> N >> M;

    cout << combination(N, M);
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!