이항계수

11050

이항계수를 구하는 방법은 몇가지가 있겠지만, 난 그냥 기억하기 편하게 백트래킹으로 풀기로 했다.

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

int n, m, count;
vector<int> vec;

void pick (int curr, int cnt) {
    if (cnt == m) {
        count++;
        return;
    }
    if (curr == n) return;

    vec.push_back(curr);
    pick(curr + 1, cnt + 1);
    vec.pop_back();

    pick(curr + 1, cnt);
}

int main() {
    cin >> n >> m;

    pick(0 ,0);
    cout << count;
}

pick함수는 5개중 2개를 백트래킹으로 고를 때 쓴다. 원래대로면 count++자리에 cout든 뭐든 문제조건에 맞는게 들어아겠지만 아무튼 이렇게 풀어도 풀린다.

11051

이번에는 수가 더 커지고, 10007로 나눈 나머지를 출력하는 문제이다.

단순히 기존풀이에 % 10007를 더했더니 시간초과가 났다.

난 시간초과가 너무 싫다.

찾아봤더니, 파스칼의 삼각형으로 푸는문제였다. 수학수업을 좀 더 열심히 들을걸 그랬다.

#include <iostream>
#define MAX 1010
using namespace std;

int n, k;
int dp[MAX][MAX];

int main() {
    cin >> n >> k;

    if (n == 0) {
        cout << 0;
        exit(0);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (j == 0) dp[i][j] = 1;
            else if (i == j) dp[i][j] = 1;
            else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    cout << dp[n][k] % 10007;
}

문제는 분명 이항계수를 10007로 나눈 값을 요구하길래 그냥 이항계수를 구하고 그걸 10007로 나누면 땡일줄 알았는데

사실은

#include <iostream>
#define MAX 1010
using namespace std;

int n, k;
int dp[MAX][MAX];

int main() {
    cin >> n >> k;

    if (n == 0) {
        cout << 0;
        exit(0);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (j == 0) dp[i][j] = 1;
            else if (i == j) dp[i][j] = 1;
            else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

            dp[i][j] = dp[i][j] % 10007;
        }
    }
    cout << dp[n][k] % 10007;
}

각 dp별로 이항계수를 10007로 나눠야했다.

왜?