[백준] 11051번
이항 계수 2
python
11051번 이항 계수1의 심화 버전이다.
11050번보다 훨씬 넓은 범위의 이항 계수의 값을 구하는 문제이다.
시간 제한이 있기 때문에 앞에서 사용한 방법보다 시간적으로 효율적인 답안을 유도한다.
문제에서 제시한 방법은 동적 계획법을 통해서 문제를 해결하도록 했다.
하지만 동적 계획법을 사용하지 않고 조합의 특수한 점을 이용하여 해결할 수 있다.
따라서 두 가지의 풀이를 제시한다.
동적 계획법을 이용한 풀이
이항 계수는 잘 알려진 것처럼 위의 형태를 띈다.
양 끝의 값은 nC0과 nCn이므로 1로 고정된다.
안쪽의 값은 동일한 규칙을 통해서 구할 수 있고 점화식은 다음과 같다.
dp[n][k] = dp[n-1][i-1] + dp[n-1][i]
따라서 점화식을 이용하면 동적 계획법을 통해 간단하게 문제를 해결할 수 있다.
조합의 특수한 점을 이용한 풀이
조합은 nCk = nCn-k 라는 특징을 가진다.
따라서 입력으로 주어진 k의 값이 크다면 n-k의 결과를 구해서 시간을 단축할 수 있다.
nCk = n(n-1)(n-2)(n-k+1)/k(k-1)...1 인 것을 이용한다.
소스 코드는 아래와 같다.
팩토리얼을 이용한 간단한 풀이
위에서 나온 조합의 계산 식을 통해서도 알 수 있지만
조합은 기본적으로 팩토리얼을 가지고 계산할 수 있다.
nCk = n!/(k!*(n-k)!)
Whiplash We Flash