[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$

소스코드

	var cache = [[Int]](repeating: [Int](repeating: 0, count: 31), count: 31)
	for i in 0...30 {
	for j in 0...i {
	if i == j || j == 0 {
	cache[i][j] = 1
	continue
	}
	cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
	}
	}
	func solution() {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let r = input[0], n = input[1]
	print(cache[n][r])
	}
	let t = Int(readLine()!)!
	for _ in 0..<t { solution() }

view raw 다리 놓기(BottomUp).swift hosted with ❤ by GitHub

	var cache = [[Int]](repeating: [Int](repeating: 0, count: 31), count: 31)
	func f(n: Int, r: Int) -> Int {
	if cache[n][r] != 0 {
	return cache[n][r]
	}
	if n == r || r == 0 {
	return 1
	}
	cache[n][r] = f(n: n - 1, r: r) + f(n: n - 1, r: r - 1)
	return cache[n][r]
	}
	func solution() {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let r = input[0], n = input[1]
	print(f(n: n, r: r))
	}
	let t = Int(readLine()!)!
	for _ in 0..<t { solution() }

view raw 다리 놓기(TopDown).swift hosted with ❤ by GitHub

후기

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