[파이썬][백준 11050번] 이항 계수 1
1. 문제Permalink
[Bronze I] 이항 계수 1 - 11050Permalink
성능 요약Permalink
메모리: 30840 KB, 시간: 68 ms
분류Permalink
조합론(combinatorics), 구현(implementation), 수학(math)
문제 설명Permalink
자연수
입력Permalink
첫째 줄에
출력Permalink
출처: 백준, https://https://www.acmicpc.net/
2. 해결방법 시간복잡도Permalink
- DP 탑다운 O(N)
3. 문제 해결 및 코드Permalink
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
input = sys.stdin.readline | |
N, K = map(int, input().split()) | |
def top_down(n, k): | |
if k > n: | |
return 0 | |
DP = [[-1 for _ in range(n + 1)] for _ in range(n + 1)] | |
def select(times, got): | |
if times == n: | |
return got == k | |
if DP[times][got] != -1: | |
return DP[times][got] | |
DP[times][got] = select(times+1, got) + select(times+1, got+1) | |
return DP[times][got] | |
return select(0, 0) | |
print(top_down(N, K)) |
-
주석을 참고하면서 이해를 돕습니다.Permalink
4. 알고리즘 및 해설Permalink
- 이항 계수란 이항식을 이항 정리로 전개했을 때 각 항의 계수
- 문제에 해결한 방법은 DP(다이나믹 프로그래밍)중 Top-Down(탑다운)이다.
- 탑다운은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식으로 메모이제이션으로 하향식이라고도 부른다.
- 여기서 사용된 방법은 DP라는 리스트를 N+1만큼의 길이로 이루어진 리스트안에 N+1 만큼의 -1로 가득찬 리스트를 만든다.
- DP라는 이중 리스트의 [time][got] 위치값으 -1이 아니라면 값을 출력하고, 이외는 다시 재귀문을 통해 값이 이항하며 식이 전개된다.
- 안에 재귀문을 통해 두 값을 넣어서 time이라는 변수가 N이 되면 got값이 N이 되어 true + true는 2라는 값을 만든다.
ReferPermalink
- Mapin의 이항 계수 1 풀이식을 참조했습니다.
- SUNGWAN PARK의 이항계수 글을 참조했습니다.