[백준 / BOJ] 11051번 이항 계수 2 (C++, Python)

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

11051번: 이항 계수 2

---

문제

---

문제 풀이

그냥 풀면 N, K가 제한이 1000이므로 시간초과가 나는 문제이다. DP를 활용해야 하는 문제인데, 동적 계획법 파트에 있었으면 좋았을 것 같은 문제다.

 

이항 계수의 점화식은 아래 사진과 같다.

여기서 dp[1][1], dp[1][0]은 미리 1로 초기화해 주고 시작하면 된다.

 

파이썬은 바로 % 10007해도 괜찮다. 내장 함수의 힘인 것 같다.

 

 

C++ 코드 전문

	#include <algorithm>
	#include <iostream>
	#include <vector>
	int dp[1001][1001];
	void init() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	}
	int main() {
	init();
	int N, K;
	std::cin >> N >> K;
	dp[1][1] = 1;
	dp[1][0] = 1;
	for (int i = 2; i <= N; ++i) {
	for (int j = 0; j <= K; ++j) {
	if (j == 0 || i == j) {
	dp[i][j] = 1;
	}
	else {
	// 매 연산마다 나눠주지 않으면 메모리 초과
	dp[i][j] = dp[i - 1][j - 1] % 10007 + dp[i - 1][j] % 10007;
	}
	}
	}
	std::cout << dp[N][K] % 10007;
	return 0;
	}

view raw 11051_이항 계수 2 (22.06.10 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	import sys
	import math
	input = sys.stdin.readline
	N, K = map(int, input().split())
	print(math.comb(N, K) % 10007)

view raw 11051_이항 계수 2 (22.06.10 성공).py hosted with ❤ by GitHub

 

소감