[코딩 테스트 연습(파이썬/Python)] 백준 11051번 _ 이항 계수 2

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

[문제]

[입력]

[출력]

[아이디어]

분모나 분자를 한 번에 계산해놓고 나눌 경우 부동 소숫점에 의한 오류가 발생하는 것 같다. 사실 N=1000, K=500인 경우 이렇게 해도 문제가 생길 것 같았는데 그렇지는 않았다.

a,b = map(int, input().split())
b = min(b, a-b)
n=1
for i in range(b):
    n*= a-i
for i in range(1, b+1):
    n//=i
print(n%10007)

실력이 퇴화하는 것 같아서 기분이 넘 별로.. 위처럼 풀면 DP를 활용하지 않은 셈이다.

a,b = map(int, input().split())
b = min(b, a-b)
dp = [[0] + [0 for _ in range(k)] for k in range(a+1)]
for i in range(1,a+1):
    for j in range(len(dp[i])):
        if(j == 0) or i==j:
            dp[i][j] = 1
        else:
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%10007
print(dp[a][b])

그래서 이렇게 n choose k를 구하기 위한 배열을 만들어 놓은 뒤, n choose k = n-1 choose k-1 + n-1 choose k 임을 이용하면 연산 부담을 훨씬 덜 주면서 해결할 수 있다. 필요에 따라 2차원 이상의 배열을 만드는 연습을 자꾸 해야한다.