(Java) Project Euler 015 - Lattice Paths

// Starting in the top left corner of a 2 X 2 grid, and only being able to move to the right and down,
// there are exactly 6 routes to the bottom right corner.

// How many such routes are there through a 20 X 20 grid?

 

Question) 

-- 2 X 2 표에서 좌상단 코너에서부터 우하단 코너까지 가는 경로를 계산하면 6개가 나온다.

-- 20 X 20 표에서 경로는 몇 개를 구할 수 있나? 

 

import java.math.BigInteger;

public class ProjectEuler_015 {
    public static void main(String[] args) {
        BigInteger result = factorial(40).divide(factorial(20).multiply(factorial(20)));        //  1)
        System.out.println(result);
    }

    static BigInteger factorial(int n) {                                                            //  2)
        if (n == 0 || n == 1) {                                                                     //  3)
            return BigInteger.ONE;
        } else {
            return BigInteger.valueOf(n).multiply(factorial(n - 1));                            //  4)
        }
    }
}

 

1) 경로 계산은 40 combination 20을 계산함.
2) 팩토리얼을 계산하는 메서드
3) 0!과 1!은 1이므로 BigInteger.ONE을 반환.
4) n! = n * (n-1)! 를 재귀적으로 계산하기.

---

조합과 경우의수는 고등학교때 정말 힘들게 배웠던 걸로 기억하고 다시는 안볼 줄 알 았는데 여기서 또 보게 되었다..