[백준 BOJ] BOJ-1010 다리 놓기

#1010 다리 놓기

 

문제 정리

 

풀이

import Foundation

let t = Int(readLine()!)!
var nm: [[Int]] = []
for _ in 0..<t {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    nm.append(input)
}

func combination(n: Int, r: Int) -> Double {
    return factorial(n) / (factorial(n - r) * factorial(r))
}

func factorial(_ n: Int) -> Double {
    return (1..<n+1).map(Double.init).reduce(1.0) { $0 * $1 }
}

nm.forEach { nm in
    print( String(round(combination(n: nm[1], r: nm[0]))).dropLast(2) )
}

m개의 사이트에서 n개의 사이트를 골라 다리를 만드는 중복없는 조합을 구하는 문제였다.

조합 공식은 다음과 같기에

combination() 과 factorial()을 구현했다.

factorial() 의 반환형을 Int 로 하면 factorial(20) 의 값이 Int64의 범위를 넘어 오버플로우가 발생하기 때문에 Double로 구현했다.

그다음 경우의 수는 소숫점이 없기 때문에 round() 함수로 반올림 처리를 해주고

숫자 뒤 .0을 지워주기 위해 String()으로 형변환 후 dropLast(n) 함수로 .0 부분을 없앴다.

시간복잡도

reduce 는 O(n) 의 시간복잡도를 갖고 있기 때문에

O(n) 이 된다.

 

풀고나서 알게된 것

이론으로만 배웠던 오버플로우를 실제로 경험하니 신기하기도 하고 난감했다.

factorial 처럼 계산값이 커지는게 예상되면 오버플로우를 생각하며 코드를 짜야겠다.