[백준 알고리즘] 11050번(이항 계수Ⅰ)

[백준 알고리즘]

오늘은 이항 계수에 대해 먼저 알아보고 문제를 한번 풀어보도록 하겠습니다.

그러기 위해서는 일단 이항 계수가 뭔지 부터 알고 가야합니다.

• 이항 계수

위키 백과사전에는 이렇게 정의가 되어있습니다.

주어진 크기의(순서 없는) 조합의 가짓수이다.

고등학교 때 분명히 했을 텐데 기억이 안나서 여기 저기 찾아봤습니다.

머리가 멍청한 건지 이해가 안돼서 정말 많이 찾아봤습니다. 그래서 정확하지 않을 수 있으니 

참고만 하시고 저 보다 더 나은 자료 찾으시길 바랍니다.

일단, 나눠서 이해를 해봤습니다. 이항 과 계수 

이항은 등식의 성질에 의해 좌변과 우변의 등식에서 어떤 한 변에 있는 항을 부호를 바꿔서 다른 변으로 옮기는 것을 말합니다.

쉽게 이해를 돕기 위해 

1 + x = 5 라는 식을 보겠습니다.

여기서 우리는 x의 값을 구하기 위해 이항을 이용해야합니다.

1이라는 항을 등식의 반대편에 넘겨야 X의 값을 구할 수 있습니다. X = 5 - 1 이런 식으로요

이렇게 하는 것을 이항이라고 합니다.

계수는 어떤 변수에 일정하게 곱해진 상수 인자입니다.

이건 더 쉽습니다.

2x³ 에서 계수는 2가 되고 5x 에서 계수는 5가 됩니다.

둘 다 보고 풀어서 쓰게되면

어떤 한 변에 있는 항을 부호를 바꿔서 다른 변으로 옮긴 어떤 변수의 항에 일정하게 곱해진 상수 인자를 말하는 것 입니다.

이건 제가 그냥 풀어 쓴거니까 믿지 마세요 그냥 쓴 겁니다.

무슨 말인지 저도 모르겠어요

이제 예를 들어 보겠습니다.

(a + b)³ 을 우리가 한번 풀어서 써보겠습니다.

(a + b)² = (a+b)(a+b)

     = a² + ab + ba + b²

     = a² + 2ab + b²

누구나 다 아실겁니다. 이 때 ab의 계수는 2가 됩니다. 당연히 그렇습니다.

그렇다면 다시 위로 올라가서 주어진 크기의(순서 없는) 조합의 가짓수이다. 정의를 보면

ab 는 a 와 b의 조합으로 이루어져 있고 그것의 가짓수(계수)는 2가 됩니다.

우리가 구하려고 하는 것이 드디어 나왔네요. 바로 2가 ab의 이항계수라는 말입니다.

이 ab의 이항계수를 구하는 방법을 알고리즘으로 짜는 것이 

11050번의 문제입니다. 그런데 위키 백과에 그 과정이 잘 정의 되어있습니다.

결국 우리가 구하고자 하는 것은 위에 정의된 내용입니다.

왜 이렇게 되는 것인지는 저도 잘 모르겠고 앞으로 좀 더 공부를 해야되는 부분일 것 같습니다.

이것을 가지고 알고리즘을 짜면 될 것 같습니다.

     

import java.util.Scanner;
 
public class Beak11050 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
 
        int result = Factorial(n) / (Factorial(n - k) * Factorial(k));
 
        System.out.println(result);
    }
 
    public static int Factorial(int n) {
        if (n == 1 || n == 0)
            return 1;
        else
            return Factorial(n - 1) * n;
    }
}
 

그냥 주어진 것과 똑같이 짰습니다.

위에 이항계수는 저 혼자 이해한 것을 적은 것이니  

혹시라도 틀린 것이 있으면 지적해주시면 감사하겠습니다.

보충 하실 말이 있어도 적어주시면 좋겠습니다.

한가지 빠진 것이 있어서 밑에 추가합니다.

이항계수를 구하는 방법은 위에 설명한 방법도 있지만 다른 방법도 있습니다.

파스칼의 삼각형 입니다.  (출처 : http://blog.naver.com/vollollov/220947452823)

이 선생님의 설명이 가장 이해하기 쉽고 잘 설명되어 있어 출처 남깁니다.

파스칼의 삼각형은 이항계수를 조금 더 쉽고 보기 좋게 해놓은 것?입니다.

이 삼각형을 보시면 규칙이 있다는 것을 알 수 있습니다. 

자기 자신의 대각선 위에 두 값을 더하면 자기 자신이 된다는 것을요.

오른쪽은 nCr의 형태로 바꾼 겁니다. 그렇게 바꾼다고 해서 규칙이 없어지는 것이 아닙니다.

즉 4C0 + 4C1 = 5C1이 된다는 것입니다. 

이것은 이 되는 것을 알 수 있습니다.

그리고 이러한 법칙을 따릅니다.

               

그렇게 되면 위에 식은   이렇게 표현이 가능합니다.

그럼 이것을 가지고 우리는 코딩을 하면 됩니다.

이렇게요!

import java.util.Scanner;
 
public class Beak11050 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
 
        int result = bincoeff(n, k);
        System.out.println(result);
 
    }
 
    public static int bincoeff(int n, int r) {
        if (n == r || r == 0)
            return 1;
        else
            return bincoeff(n - 1, r - 1) + bincoeff(n - 1, r);
    }
}
 

그럼 수고하세요