11051번 이항계수2(DP) - ☆

#문제링크 : https://www.acmicpc.net/problem/11051

<전략>

1. N이 1000까지 가능하므로, 수가 어마어마하게 커진다. 따라서, 일반적인 재귀로는 시간초과가 된다.

2. 메모이제이션과 이항계수의 특징을 활용하여 C[N][K]라는 2차원 배열을 만들고 C[N][K]  = C[N-1][K] + C[N-1][K-1] 임을 이용하여 배열에 저장한다.

3. 파스칼의 삼각형에서 삼각형의 양옆 변두리(nC0, nCn = 1)값만을 1로 저장해주면 나머지 배열의 값들은 위의 식 연산을 통해 자동으로 저장된다.

Code