-
BOJ 11051 이항 계수 2알고리즘/백준 2021. 12. 27. 16:22
11051번: 이항 계수 2
첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\))
www.acmicpc.net
이항 계수 문제.
이항 계수는 (x+y)^n의 식을 세웠을 때
0과 n의 위치는 항상 1이고
나머지 1~n-1까지의 값은 임의의 값 k를 뒀을 때
(x+y)^n-1의 계수들 중 k-1, k 위치의 계수를 더한 값이 나온다.
이렇게 만들어낸 것을 파스칼의 삼각형이라고 부르며 다음과 같이 나오게 된다.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
일단 조건을 먼저 파악한 결과 방정식의 최대 지수가 1000이라는 것을 먼저 파악했다.
여기서 최대 이중 반복문을 써도 제한 시간 내에 해결할 수 있고, 그에 따라 방법을 먼저 생각해보았다.
사실, 이항 계수는 Dynamic Programming을 통해 쉽게 해결할 수 있는 문제였다.
점화식은 다음과 같다.
dp[n][k] = dp[n-1][k-1] + dp[n-1][k]
그래서 Bottom-Up 방식으로 차례차례 계산을 행한 후
n,k를 집어 넣어줌으로써 solve 판정을 받았다.
'알고리즘 > 백준' 카테고리의 다른 글
BOJ 21921 블로그 (0) 2022.02.11 BOJ 1238 파티 (0) 2022.01.28 BOJ 9177 단어 섞기 (0) 2022.01.26 BOJ 1613 역사 (0) 2022.01.21 BOJ 11404 플로이드 (0) 2022.01.20