[swift] 백준 - 11050번: 이항 계수 1

11050번: 이항 계수 1

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

문제 설명

 

이항 계수를 구하는 문제입니다.

로 읽을 수 있습니다.

 

이항계수를 이해하기 위해서는

파스칼의 삼각형과 이항 정리의 개념을 짚고 넘어오시는걸 추천합니다.

 

이항계수의 공식

 

개념을 이해하셨다면

 

 

팩토리얼을 사용하여 이항계수를 구하는 공식이 있습니다.

해당 식을 사용하여 문제를 풀었습니다.

 

나의 풀이

var NK = readLine()!.split(separator: " ").map { Int($0)! }
func factorial(num: Int) -> Int {
    guard num > 1 else { return 1 }
    var result = 1
    for i in 2...num { result = result * i }
    return result
}
print(factorial(num: NK[0]) / (factorial(num: NK[1]) * factorial(num: (NK[0] - NK[1]))))

 

---

 

다른 형태의 팩토리얼

func factorial(num: Int) -> Int{
    if num <= 1 { return 1 }
    return num * factorial(x-1)
}

(1...Int(readLine()!)!).reduce(1,*)

 

다양하게 팩토리얼을 구현할 수 있었습니다.

 

다르게는

다이나믹 프로그래밍 기법으로

 

let nm = readLine()!.split(separator: " ").map{Int($0)!}
var arr = Array(repeating: 1, count: 20)
for i in 1...nm[0] {
    let tmp = arr
    for j in 1..<i {
        arr[j] = tmp[j] + tmp[j-1]
    }
}
print(arr[nm[1]])

 

팩토리얼 함수를 따로 만들지 않고

메모리를 사용하여 피보나치 수열을 저장하고

원하는 값을 뽑아 쓸 수 있었습니다.