[BOJ]11050 이항계수1 (kotlin)

11050번: 이항계수1

이번에는 이항계수에 대한 문제를 풀었다.

처음에는 이항계수가 뭔가 했는데 아래와 같은 정의를 가진다.

조합론에서 이항 계수(binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

음,, 무슨소린지 모르겠다. 😅

알아보기 쉽게 분리해서 정리하자면 아래와 같다.

의미1)

• 다항식의 계수

의미2)

• 주어진 원소들의 순서 없는 조합의 경우의 수
• nCr, C(n,r) : n개의 원소 중 r 개를 순서 없이 선택하는 경우의 수

이 문제에서는 의미2를 구하는게 목적이었다!

이항계수는 일반적으로 아래와 같은 수식으로 구할 수 있다.

\[C(n,r)=n!/(r!*(n-r)!)\]

팩토리얼을 사용한 이항계수 알고리즘

이항계수를 구하는데에는 여러 알고리즘이 있지만, 이 문제와 같이 입력케이스가 하나밖에 없는 경우 기존 계산 내용을 재활용하는 동적 프로그래밍의 장점이 발휘되지 않으므로 팩토리얼로 위 수식을 구현하는것이 간편해 보였다.

아래는 팩토리얼을 사용해 이항계수 공식을 구현한 것이다.

fun main(){

    val (n,k)=readLine()!!.split(" ").map{it.toInt()}
    print(getBinomialCoefficient(n,k))

}

fun getBinominalCoefficient(n:Int,k:Int):Int{
    return getFactorial(n,k)/getFactorial(k)
}

fun getFactorial(n:Int,limit:Int=n):Int{
    var res=1
    for(i in 0 until limit){
        res*=n-i
    }
    return res
}

🤔이중 getFactorial()에 있는 limit는 $n!/r!$을 따로 연산하여 처리하는것보다 이렇게 반복횟수에 제한을 두어 한번에 처리하면 연산량과 시간이 줄어들 것 이라고 생각해서 위와 같이 짜봤다.

이 함수의 시간 복잡도는 getFactorial() 함수에 의해 결정되므로 O(n)이고 이때 시간은 132ms가 걸렸다.

🚀Advanced

이 문제는 이항계수를 구하는 getBinomialCoefficient()에서 개선의 여지가 있었다.

나의 경우 getFactorial()이라는 함수를 호출해서 각각의 항목에 대해 팩토리얼값을 얻었지만 아래와 같이 쓴다면 한번의 반복문으로 이항계수 공식을 구현할 수 있다.

fun getBinominalCoefficient(n:Int,k:Int):Int{
	var res=1
	for(i in 1 .. n-k){
		res*=n-(i-1)
		res/=i
	}
}

여기에서는 위의 수식을 다음과 같이 표현하면 이해가 좀 쉽다.

\[C(n,r)=n!/r!  ×  1/(n-r)!\]

여기서 (n!/r!)과 (n-r)!은 계산하기 위한 반복 횟수가 (n-r)번으로 같으므로 하나의 반복문 안에서 한번에 계산할 수 있는 것 이다!

이 방법의 시간 복잡도는 처음 방법과 같이 O(n)이고, 백준 실행 시간은 그대로 132ms로 줄어들지는 않았다.🥲

그러나 반복문의 개수가 줄었기 때문에 상수항이 줄어서 입력이 커진다면 이렇게 구현하는것이 효율이 좋을것이라고 생각한다!