파스칼 삼각형

 

파스칼 삼각형은 이항계수를 쉽게 구하는 방법이다

이항계수의 의미를 잘 안다면 파스칼 삼각형의 원리를 이해할 수 있다

n개에서 순서 상관없이 k개를 뽑는 경우는 n을 포함하는 경우, n을 포함하지 않은 경우로 나눠진다

n을 포함하는 경우는 남은 n-1개 k-1개를 뽑는 것이고, n을 포함하지 않은 경우는 n-1개에서 k개를 뽑는 경우다

 

d[n][k] = d[n-1][k-1] + d[n-1][k]와 같은데 이것을 삼각형과 같이 도식화 한 것이다

 

예제문제: https://www.acmicpc.net/problem/11051

깃허브주소: https://github.com/surinoel/boj/blob/master/11051.cpp