[Swift] 백준 2004 - 조합 0의 개수

문제 링크

수능이 까마득해서리,, 조합이 뭔지 기억도 안났다

• 여기의 nCr이 조합!!

조합이 팩토리얼로 구성되어 있기에
이전의 팩토리얼 0의 개수 구하기를 조금 변형하여 구하려고 했다!

입력받은 수 n, m이 있을 때 (n>m)
(n-m)부터 n까지의 5, 5^2, 5^3...의 개수를 구하고
1에서 (n-m)까지의 5, 5^2, 5^3...의 개수를 구해 빼주려고 했다

근데 계속해서 오류가 나는 것이다....
그래서 생각해보니, 팩토리얼 0의 개수 구하기에서의 전제인
'2가 항상 5보다 많다'가 여기서는 항상 참이 아닐 수도 있다는 점을 빼먹었다ㅠㅠ

그래서 이번엔, 2의 개수와 5의 개수를 둘 다 구해서 둘 중 더 적을 것을 출력해주기로 하였다

초기 풀이(시간초과남)

import Foundation

let nums = readLine()!.split(separator: " ").map{Int(String($0))!}

let n = nums[0]
let m = nums[1]

func get2(_ num: Int) -> Int {
    var count = 0
    
    for i in 1..<num+1 {
        var temp = i
        while temp>0,temp%2==0 {
            count += 1
            temp /= 2
        }
    }
    return count
}



func get5(_ num: Int) -> Int {
    var count = 0
    
    for i in 1..<num+1 {
        var temp = i
        while temp>0,temp%5==0 {
            count += 1
            temp /= 5
        }
    }
    
    return count
}

let a = get2(n) - (get2(m)+get2(n-m))
let b = get5(n) - (get5(m)+get5(n-m))

print(a>b ? b : a)

• 테스트케이스 제대로 풀리는데 시간이 초과가 되었다.
  그래서 하나하나 2나 5로 나눈 값을 더하지 않고, 5, 25, 125...로 나눠지는 몫을 한번에 더하는 방법으로 바꾸었다

최종 풀이

import Foundation

let nums = readLine()!.split(separator: " ").map{Int(String($0))!}

let n = nums[0]
let m = nums[1]

func get2(_ num: Int) -> Int {
    var count = 0
    var i = 2
    while num >= i {
        count += num/i
        i *= 2
    }
    
    return count
}



func get5(_ num: Int) -> Int {
    var count = 0
    var i = 5
    while num >= i {
        count += num/i
        i *= 5
    }

    return count
}

let a = get2(n) - (get2(m)+get2(n-m))
let b = get5(n) - (get5(m)+get5(n-m))

print(a>b ? b : a)

이렇게 바꿔주면 제대로 통과가 된다..! (야호..)