Project Euler Problem 15 : 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

---

Project Euler 문제를 해답을 포스팅합니다.

※ 주의 : 최적화는 할 수 있는 만큼했습니다. 따라서 속도면에서는 많이 부족합니다.

           문제를 푸는데 목표를 두었고 또한 TDD를 최대한 활용하였습니다.

           몇가지 문제의 경우 TDD를 안한 경우도 있습니다.

           혹시, 최적화 또는 속도 증가에 대한 부분을 지적해주실 분은 너무나도 감사합니다.

---

Project Euler Problem 15

아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?

---

이 알고리즘 문제는 고등학교때 최단거리 구하기 문제에서 기본입니다. 순열을 이용하면 구할 수 있으므로 20x20 격자의 경우의 수는 40! / 20! x 20! 입니다.

근데 전 40!이 엄청 큰 수더라구요;; 문자열로 계산 할까 했지만 double을 이용하여 쉽게 계산하고 유효숫자에서 소수점 단위가 남기때문에 long으로 형변환하여 문제를 풀었습니다.

파이썬의 경우;; 단번에 풀린다고 합니다.

---

Source Code

Main Class Code

public class Main { 
    public static void main(String [] args) {
        double result = 1;
        for(int i=21; i<=40; i++) { 
            result *= i; 
        } 
         
        for(int i=1; i<=20; i++) { 
            result /= i; 
        } 
         
        System.out.println((long)result); 
    } 
}