solved_ac[Class2][이항 계수 1](https://www.acmicpc.net/problem/11050)
자연수 N과 정수 K가 주어졌을 때 이항 계수
(N K)를 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N)
(N K)를 출력한다.
5 2
10
itertools의 combinations 함수를 쓰면 쉽게 풀 수 있으며, factorial을 써도 쉽게 풀 수 있다. 하지만 문제에서 dp를 이용해서도 풀 수 있기 때문에 dp에 대해 알아보자.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
a(n) = a(n-1) + a(n-2), a(1) = 1, a(2) = 1
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))
메모이제이션 (Memoization)
탑다운 VS 보텀엄
d = [0] * 100
def fibo(x):
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n + 1):
d[i] = d[i -1] + d[i - 2]
print(d[n])
d = [0] * 100
def fibo(x):
print('f(' + str(x) + ')', end = ' ')
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
fibo(6)
f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)
import sys
import itertools
N, K = map(int, sys.stdin.readline().split())
res = len(list(itertools.combinations(range(1, N + 1), K)))
print(res)
import sys
N, K = map(int, sys.stdin.readline().split())
def fact(num):
if num == 0:
return 1
if num == 1:
return 1
else:
return num * fact(num - 1)
print(fact(N) // (fact(K) * fact(N - K)))
import sys
N, K = map(int, sys.stdin.readline().split())
dp = [[0] * 11 for _ in range(11)]
for i in range(N):
for j in range(i + 1):
if i == j:
dp[i][j] = 1
# 위 그림에서 보이는 맨 오른쪽 대각선 수 들
elif j == 0:
dp[i][j] = i + 1
# 위 그림에서 보이는 맨 왼쪽 대각선 수 들
else:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
# 점화식
if K == 0:
print(1)
else:
print(dp[N - 1][K - 1])
이 문제가 굳이 dp로 풀지 않아도 되는 것은 안다. 하지만 dp는 코딩 테스트에서 가장 중요하고 골드 단계로 올라가게 되면 계속 해서 나오는 유형이기 때문에 미리 익혀두는게 나쁘지 않을 것이라고 생각하여서 포스팅을 한 것이다.