[실전 문제] combinationpascal

1. 문제

n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.

 

이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다.

 

n과 m이 주어졌을때 nCm의 값을 출력하는 프로그램을 작성하시오.  

---

입력

첫째 줄에 정수 n, m(0 ≤ m ≤ n ≤ 30)이 들어온다.

출력

첫째 줄에 nCm의 값을 출력한다.

예제 입력

5 2

예제 출력

10

 

 

 

2. 풀이

이 문제는 팩토리얼로 계산할 경우, 어마어마한 계산량이 요구될 수 있기 때문에 파스칼 삼각형으로 풀어야한다. 그러기 위해서는 파스칼 삼각형과 조합간의 관계를 살펴보아야한다.

 

그림과 같이 파스칼 삼각형에서 20은 그 위 두 숫자, 10의 합임을 알 수 있다. 또한, 각 층에 해당하는 모든 값들은 조합의 결과인 것도 알 수 있다.

5C0	5C1	5C2	5C3	5C4	5C5
1	5	10	10	5	1

 

따라서 6C3 = 5C2 + 5C3으로 표현할 수 있다. 이를 공식화하여 코드에 녹이면 해결이 가능하다.

• nCm = (n-1)C(m-1) + (n-1)Cm

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        bw.write(pascal(n, m) + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static int pascal(int n, int m) {
        // 5C2
        // = 4C2 + 4C1
        // = 3C2 + 3C1 + 4C1
        // = 2C2 + 2C1 + 3C1 + 4C1

        if(n == m || m == 0) return 1;
        if(m == 1) return n;

        return pascal(n-1, m) + pascal(n-1, m-1);
    }

}