PS
백준 11051. 이항 계수 2
tose33
2022. 9. 26. 15:09
https://www.acmicpc.net/problem/11051
11051번: 이항 계수 2
첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\))
www.acmicpc.net
파스칼의 삼각형을 이용해서 푼다.
파스칼의 삼각형의 n행k열은 nCk (n개 숫자중 k개를 뽑는 경우)를 나타낸다.
예를들어 5C2를 구해보면 위 파스칼의 삼각형에서 5행 2열은 10이다. (0행 0열부터 시작)
점화식은 d[i][j] = d[i-1][j-1] + d[i-1][j]
물론 인덱스가 음수가 되는 경우는 처리해줘야 한다.