이항 계수 2.md

DONE_DATE
2024/07/07, 2025/01/04

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

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
using namespace std;  
  
int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
  
    int n, k;  
    cin >> n >> k;  
  
    vector<vector<int>> v;  
  
    for (int i = 0; i < n + 1; i++) {  
        vector<int> temp;  
        temp.push_back(1);  
        for (int j = 1; j <= i; j++) {  
            temp.push_back((v[i - 1][j - 1] + v[i - 1][j]) % 10007);  
        }  
        temp.push_back(0);  
        v.push_back(temp);  
    }  
  
//    for (auto i: v) {  
//        for (auto j: i) {  
//            cout << j << " ";  
//        }  
//        cout << endl;  
//    }  
  
    cout << v[n][k] % 10007 << endl;  
  
    return 0;  
}

추가 : 2025/01/04

#include <bits/stdc++.h>

typedef long long ll;
#define MOD 10007
using namespace std;

ll binomial(int N, int K) {
    int old_dp[N + 1];
    int new_dp[N + 1];

    old_dp[0] = 1;

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || i == j) {
                new_dp[j] = 1;
            } else {
                new_dp[j] = (old_dp[j] + old_dp[j - 1]) % MOD;
            }
        }

        for (int j = 0; j <= N + 1; j++) {
            old_dp[j] = new_dp[j];
        }
    }
    return new_dp[K];
}

int main() {
    int N, K;
    cin >> N >> K;
    cout << binomial(N, K);
}

풀이

• 이항계수 1에 나머지가 추가가 되었다.
• 이항계수 1보다 빠르게 계산을 해야한다.
• DP를 사용하는 문제이다.
• 파스칼의 삼각형을 생각하면된다.
• v[i][j] = v[i-1][j-1] + v[i-1][j] 이다.

01/04 풀이

• 조금더 예쁜 방식이라고 생각한다.
• old_dp와 new_dp를 사용하여 이전값과 현재값을 저장한다.
• new_dp에 값을 저장하고 old_dp에 new_dp를 복사한다.
• 연산은 new_dp[j] = (old_dp[j] + old_dp[j - 1]) % MOD; 이다. (파스칼의 삼각형)