[파이썬][백준 11050번] 이항 계수 1

1. 문제

[Bronze I] 이항 계수 1 - 11050

문제 링크

성능 요약

메모리: 30840 KB, 시간: 68 ms

분류

조합론(combinatorics), 구현(implementation), 수학(math)

문제 설명

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $(\genfrac{}{}{0ex}{}{N}{K})$를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$과 $K$가 주어진다. (1 ≤ $N$ ≤ 10, 0 ≤ $K$ ≤ $N$)

출력

$(\genfrac{}{}{0ex}{}{N}{K})$를 출력한다.

출처: 백준, https://https://www.acmicpc.net/

2. 해결방법 시간복잡도

1. DP 탑다운 O(N)

3. 문제 해결 및 코드

---

• 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

• 이항 계수란 이항식을 이항 정리로 전개했을 때 각 항의 계수

1. 문제에 해결한 방법은 DP(다이나믹 프로그래밍)중 Top-Down(탑다운)이다.
   • 탑다운은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식으로 메모이제이션으로 하향식이라고도 부른다.
2. 여기서 사용된 방법은 DP라는 리스트를 N+1만큼의 길이로 이루어진 리스트안에 N+1 만큼의 -1로 가득찬 리스트를 만든다.
3. DP라는 이중 리스트의 [time][got] 위치값으 -1이 아니라면 값을 출력하고, 이외는 다시 재귀문을 통해 값이 이항하며 식이 전개된다.
4. 안에 재귀문을 통해 두 값을 넣어서 time이라는 변수가 N이 되면 got값이 N이 되어 true + true는 2라는 값을 만든다.

Refer

• Mapin의 이항 계수 1 풀이식을 참조했습니다.
• SUNGWAN PARK의 이항계수 글을 참조했습니다.

5. 짚고 넘어가기