코딩테스트
2022. 1. 13.
[C++] (백준 11051 번) 이항 계수 2
문제출처: 백준 문제 링크: https://www.acmicpc.net/problem/11051 난이도: ★★☆☆☆ 문제 분류: 다이나믹 프로그래밍 (dp) [문제] [분석] 항상 풀던 dp문제이다.base case의 경우, 이항계수의 기본 성질을 base case로 하면 된다.또한, n>k가 되면 이항계수를 구할 수 없다. 다음의 경우가 BASE CASE가 된다. Recursive case의 경우 다음 표를 보면 담번에 이해된다. 다음 같은 규칙이 성립되는 이유는 다음과 같다. 규칙을 이항계수 식으로 표현하면 다음과 같다. 이 공식을 조합 규칙에 따라 변환한 뒤, 풀어보았다. 다음 공식으로 테이블의 법칙은 증명가능하다. 이제 점화식을 구하면 다음과 같다. 점화식 [코드] #include using na..