[Baekjoon Online Judge] 백준 11051번 이항 계수 2(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11051번 이항 계수 2

(C++, Python)

(글쓴날 : 2020.04.22)

 

---

* Baekjoon Online Judge, 백준 11051번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11051번 이항 계수 2

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

---

2) 풀이 과정

* 시간 복잡도 : O(n), O(n²)

 

자연수 N과 정수 K가 주어질 때, N과 K의 이항 계수를 10007로 나눈 나머지를 구하는 문제입니다.

 

저의 경우, 동적계획법을 적용하였으며, C++과 Python을 사용했습니다.

이항 계수는 조합을 의미하므로 memoization을 통해 nCk를 구해주시면 됩니다.

Python의 경우, 아무 생각 없이 팩토리얼 계산이 가능하기 때문에 시간 복잡도를 O(n) 만에 해결할 수 있으나,

C++의 경우, 연산 결과가 타입 범위를 초과해 런타임 에러가 발생하므로, 시간 복잡도가 O(n²)인 파스칼의 삼각형을 이용해 해결해야 합니다.

파스칼의 삼각형을 이용한 점화식은 제 C++ 코드 기준 memoization[i][j] = (memoization[i - 1][j - 1] + memoization[i - 1][j])이며, memoization을 위한 2차원 테이블에 해당 점화식을 적용한 반복문을 돌려 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
 
using namespace std;
 
int memoization[1001][1001];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0, K = 0;
    cin >> N >> K;
 
    for (int i = 1; i < N + 1; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            if (i == j || !j)
            {
                memoization[i][j] = 1;
                continue;
            }
            memoization[i][j] = (memoization[i - 1][j - 1] + memoization[i - 1][j]) % 10007;
        }
    }
 
    cout << memoization[N][K];
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
N, K = map(int, input().split())
memoization = [1] + [0] * (N)
 
for i in range(1, N + 1):
    memoization[i] = memoization[i - 1] * i
 
print(memoization[N] // (memoization[N - K] * memoization[K]) % 10007)

---