태그:
이항계수 \(\begin{pmatrix}N\\K\end{pmatrix}\)를 구하는 문제입니다. 이 문제는 10007로 나눈 나머지라는 조건이 붙어있기 때문에 11050번: 이항 계수처럼 곱셈과 나눗셈을 사용하여 값을 구하기는 까다롭습니다. 그래서 나머지에 친화적인 연산인 덧셈을 이용하여 풀어야 합니다. 이를 위해서는 이항 계수의 성질인 \(\begin{pmatrix}N\\K\end{pmatrix}=\begin{pmatrix}N-1\\K-1\end{pmatrix}+\begin{pmatrix}N-1\\K\end{pmatrix}(\begin{pmatrix}n\\0\end{pmatrix}=\begin{pmatrix}n\\n\end{pmatrix}=1)\)를 사용합니다. 언뜻 보면 재귀적인 성질입니다. 이 값들을 DP 배열을 선언(변수가 2개니 당연히 2차원이겠죠?)하여 저장해가면서 값을 재귀적으로 구합니다. 여기서 유의해야 할 점은 항상 10007로 나눈 나머지를 저장해야 한다는 것이겠습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-02 12:39:33 |