3-7: 파스칼의 삼각형과 조합

파스칼의 삼각형과 조합 (combinationpascal.cpp)

 

문제

---

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

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

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

입력

---

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

 

출력

---

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

 

예제 입력

5 2

예제 출력

10

import java.util.Scanner;

public class combinationpascal {

    /**
     * n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.
     *
     * 이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다.
     *
     * n과 m이 주어졌을때 nCm의 값을 출력하는 프로그램을 작성하시오.
     *
     * 첫째 줄에 정수 n, m(0≤m≤n≤30)이 들어온다.
     * 첫째 줄에 nCm의 값을 출력한다.
     *
     * 5 2
     *
     * 10
     *
     * @param args
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] cTable = new int[31][31];
        System.out.println(combinationR(cTable, n,m));

    }

    private static int combinationR(int[][] C, int n, int m) {
        if (m==1){
            C[n][m] =n;
            return n;
        }
        if (m==0){
            C[n][m] =1;
            return 1;
        }
        if (n==m){
            C[n][m] =1;
            return 1;
        }

        if (C[n][m] != 0){
            return C[n][m];
        }

        //pascal
        //1
        //1 1
        //1 2 1
        //1 3 3 1
        //1 4 6 4 1

        //add above and above adjacent
        C[n][m] = combinationR(C, n-1, m) + combinationR(C, n-1, m-1);

        return C[n][m];

    }

    private static long combination(int n, int m) {

        int mRev = n - m;
        if (mRev < m) return (combination(n,mRev));

        long top=1, bot=1;

        for (int i=1; i<=n; i++){
            if (i <=m) bot*=i;
            else if (i>n-m) top*=i;
        }

//        for (int i=n; i>n-m;i--){
//            top*=i;
//        }
//        for (int i=m; i>0;i--){
//            bot*=i;
//        }
        System.out.println(top);
        System.out.println(bot);

        return top/bot;
    }
}