[BOJ] 백준 1010 다리 놓기 (Swift)

문제

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

풀이

문제를 잘 살펴보면 조합의 수를 구하는 문제라는 것을 이해할 수 있습니다.

즉, $_mC_n$을 구하는 문제입니다.

$mCn = \frac{m!}{n!(m-n)!$ 을 구해주면 되겠죠?

하지만 입력이 최대 30이므로, $30! = 2.6525285981×10^{32}$이므로 Int 자료형의 범위를 넘어갑니다.

조합의 성질을 이용해서 구해주어야 합니다.
$nC_0 = 1, _nC_n = 1$ 이고, $_nC_r = _{n-1}C_r + _{n-1}C{r-1}$ 의 성질을 이용해서

다이나믹 프로그래밍을 사용해 구해줄 수 있습니다.

다이나믹 프로그래밍은 점화식만 구한다면 쉽게 풀 수 있습니다.

점화식 : $f(n, r) = f(n-1,r-1)+f(n-1,r)$
초기값 : $f(n, 0) = 1, f(n, n) = 1$

소스코드

후기

조합의 수를 구하는 문제입니다.
조합의 성질을 사용해 다이나믹 프로그래밍으로 풀이할 수 있었습니다.
탑 다운과 바텀 업 방식 두 가지를 사용해서 풀이해보았습니다.