BOJ : 2004 조합0의 개수 (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().trim().split(' ');
const c = console.log
33
let lst = []

for (v of input){
    lst.push(Number(v))
}

k = lst[0]
n = lst[1]
kn = k-n

mod5 = (num) => {
    count = 0
    while (num >= 5){
        count += parseInt(num/5)
        num = parseInt(num)/5
    }
    return count
}

mod2 = (num) => {
    count = 0
    while (num >= 2){
        count += parseInt(num/2)
        num = parseInt(num)/2
    }
    return count
}

countTwo = mod2(k) - (mod2(n) + mod2(kn))
countFive = mod5(k) - (mod5(n) + mod5(kn))

if (countTwo >= countFive){
    sub = countTwo - countFive
    c(countTwo - sub)
} 
else {
    sub = countFive - countTwo
    c(countFive - sub)
}

 

풀이

조합의 식은 n!/(n-r)!r! 이기 때문에 나눴을때 2와 5가 같이 있어야만 0을 구성할 수 있습니다.

그래서 숫자들의 2가 몇개 있는지 5개 몇개 있는지 갯수를 세준 후 연산을 통해서 2와5의 짝 갯수를 출력하면 됩니다.

 

문제

https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

예제 모음

input : 8 1 
output : 0

8 2
0

10 5
0

8 4
1

12 7 
0

7 3
0

12 2
0

20 10
0