[백준 / 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++ 코드 전문

 

Python 코드 전문

 

소감