백준 1010 다리 놓기
23 Jun 2021https://www.acmicpc.net/problem/1010
n개의 서쪽 지점과 m개의 동쪽 지점의 점들을 잇는 다리를 짓는 경우의 수를 찾는 문제이다. 이 때 다리는 서로 교차할 수 없다고 주어졌기 때문에 문제를 간단히 풀 수 있다.
생각해보면 m개의 동쪽 지점에서 n개를 선택하게 되면 자동적으로 가장 위에 지점부터 서쪽 지점의 가장 위쪽 지점과 연결해야 다리가 교차하지 않는다는 것을 알 수 있다. 따라서 mCn을 구하는 문제로 바꿀 수 있고 간단히 이항계수를 구해주면 해결된다.
- 전체 코드
let n = Int(readLine()!)!
for i in 1...n {
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
var arr = Array(repeating: 1, count: 31)
for p in 1...nm[1] {
let tmp = arr
for q in 1..<p {
arr[q] = tmp[q] + tmp[q-1]
}
}
print(arr[nm[0]])
}