[Project Euler] Problem 015

 

 

 

를 계산하면 된다.

 

문제는 분자의 값이 너무 커서 8바이트 자료형으로도 저장할 수 없다는 것.

따라서 40!과 20!20!을 한 번에 계산하고 나누는 것이 아니라 하나씩 나눈다.

 

public class Problem015 {
    private static final int V = 20;
    private static final int H = 20;
    
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static String run() {
        long result = 1L;
        
        for(int i = 0; i < H; ++i) {
            result *= (H + V - i);
            result /= (i + 1); 
        }
        
        return Long.toString(result);
    }
    
}

 

정답: 137846528820

 

계산은 다음과 같이 진행된다.

 

i = 0

result *= 40; //result: 40

result /= 1; //result: 40÷1 =  40

 

i = 1

result *= 39; //result: (40×39)÷1

result /= 2; //result: (40×39)÷(1×2)

 

i = 2

result *= 38; //result: (40×39×38)÷(1×2)

result /= 3; //result: (40×39×38)÷(1×2×3)

 

...

 

i = 18 

result *= 37; //result: (40×39×38×…×23×22)÷(1×2×3×4×…×18)

result /= 19; //result: (40×39×38×…×23×22)÷(1×2×3×4×…×18×19)

 

i = 19 

result *= 37; //result: (40×39×38×…×23×22×21)÷(1×2×3×4×…×18×19)

result /= 20; //result: (40×39×38×…×23×22×21)÷(1×2×3×4×…×18×19×20)

 

 

BigInteger 클래스를 쓰면 다음과 같다.

 

import java.math.BigInteger;
 
public class P015 {
    public static void main(String args[]) {
        System.out.println(run());
    }
    
    public static String run() {
        return fac(40).divide(fac(20).multiply(fac(20))).toString();
    }
    
    public static BigInteger fac(int n) {
        BigInteger res = BigInteger.ONE;
        for(int i = 2;
            i <= n;
            res = res.multiply(BigInteger.valueOf(i++)));
        return res;
    }
}

 

9행:

 fac(int n) 은  n! 을 BigInteger 형태로 반환한다.

따라서  fac(40).divide(fac(20).multiply(fac(20))).toString() 은

40!/20!20!을 문자열로 변환한 것이다.

 

12행:

주어진 정수 parameter에 대해 팩토리얼 값을 반환하는 메소드.

 

13행:

 BigInteger.ONE 은  BigInteger  클래스에 선언된 상수 필드로 정수 1을 나타낸다.

 

14~16행:

1로 초기화 된  res 에 2 ~ n을 곱한다.

따라서  res 는  n! 에 대한  BigInteger  객체를 참조하게 된다.