[python] 백준 11051 - 이항계수 2

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

11051번: 이항 계수 2

 

 

먼저, 생각해야 할 부분

 

1. 나눗셈 연산은 부동소수점 에러를 일으킬 수 있다.

 

 

---

 

풀이

 

n, k = map(int, input().split())

dp = [1 for _ in range(n+1)]

for i in range(1, n+1):
  dp[i] = (dp[i-1] * i)

print((dp[n] // (dp[n-k] * dp[k]))  % 10007)

 

그냥 팩토리얼을 쭉 구해서 조합 계산식을 돌리는 풀이이다. 

마지막에 / 연산 시행 시, 나눗셈 연산에서 추측하건데 부동 소수점 에러로 틀렸습니다가 나오는 듯 하다.

몫 연산(몫 연산)으로 바꾸어주어 통과하였다.

 

풀이 2

 

n, k = map(int, input().split())

dp = [[1 for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, n+1):
  for j in range(1, i):
    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007

print(dp[n][k])

 

파스칼 삼각형을 이용한 풀이이다.

좀 더 최적화해 줄 수 도 있었겠지만 일단은 이렇게 풀었다.

 

---

시간 복잡도

팩토리얼 풀이 : O(N)

파스칼 삼각형 풀이 : O(N^2)

 

알게 된 점

 

//

 

나눗셈 연산이 사용될 경우, 부동 소수점 에러에 주의하여야한다.

최대한 나눗셈 연산을 없애거나 몫 연산으로 대체 가능한지 생각해보자.

 

고찰

 

-

 

Github

백준 11051 - 이항 계수2