[백준] 16395번 파스칼의 삼각형

💡문제접근

이항계수에 대한 문제로 다이나믹 프로그래밍을 이용하면 시간복잡도를 줄여 효율적인 코드를 작성할 수 있다.

정수 n과 k가 주어졌을 때 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 이항계수를 이용해서 표현하면 이항계수 C(n-1, k-1)가 된다는 사실을 문제에서 미리 알려주어 쉽게 접근할 수 있었다.

💡코드

n, k = map(int, input().split())
dp = [0 for i in range(31)]
dp[0] = 1	# 0! = 1이므로 dp[0] = 1을 저장
for i in range(1, 31):
    dp[i] = i * dp[i-1]

print(dp[n-1] // (dp[n-k] * dp[k-1]))