ACM ICPC 2000 ASIA Practice Problem B Cross a Creek

Source Code

import java.util.Scanner;

public class CrossCreek{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);       

        int t = scan.nextInt();    // 테스트 케이스 개수

        for(int i = 0; i < t; i++) {
            int n = scan.nextInt();    // 개울의 너비

            process(n);
        }
    }

    public static void process(int n) {
        // 모든 경우를 구한다.
        long sum = 0;
        for(long i = n, r = 0; i >= r; i--, r++){
            sum += combination(i, r);
        }

        System.out.println(sum);
    }

    // 팩토리얼을 구한다.
    // n! = n * (n-1) * (n-2) * ... * 2 * 1
    // ex) 4! = 4 * 3 * 2 * 1 = 24
    public static long factorial(long n){
        if(n <= 1){
            return 1;
        }
        return n * factorial(n - 1);
    }

    // 조합을 구한다.
    // nCr = nPr / r! = n! / ((n-r)! * r!)
    // ex) 4개 중에 2개를 고르는 경우의 수 = 6가지
    public static long combination(long n, long r){
        return factorial(n) / (factorial(n - r) * factorial(r));
    }
}

Comment

문제를 보고 고민을 하다가 조합으로도 풀 수 있단것을 알게되었다. 수학책을 찾아보고 조합 공식에 맞춰 함수를 작성하였다.