[Project Euler] Problem 016

public class Problem016 {
    private final static int A = 2; 
    private final static int N = 1000; 
    
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static String run() {
        int[] arr = new int[350];
        int sum = 0;
        
        /*Initialize array by -1*/
        for(int i = 0; i < (arr.length - 1); ++i) {
            arr[i] = -1;
        }
        
        arr[arr.length - 1] = 1;
        
        /*Repeat N times*/
        for(int i = 1; i <= N; ++i) {
            
            /*Multiple A*/
            for(int j = (arr.length -1); arr[j] >= 0; --j) {    
                arr[j] *= A;
            }
            
            for(int j = (arr.length -1); (arr[j] >= 0) && (j > 0); --j) {
                if(arr[j] >= 10) {
                    if(arr[j - 1] < 0) {
                        arr[j - 1] = (arr[j] / 10);
                    } else {
                        arr[j - 1] += (arr[j] / 10);
                    }
                    
                    arr[j] %= 10;
                }
            }
        }
        
        for(int i = 0; i < arr.length; ++i) {
            if(arr[i] != -1) { 
                sum += arr[i];
            }
        }
        
        return Integer.toString(sum);
    }
 
}

정답: 1366

실행 시간: 10ms = 0.01초

기본적으로 수를 다음의 형태로 본다.

배열에는 각 자리의 수  m 을 저장하고, 지수는  n - index 로 나타낸다.

여기서 n은 배열의 길이다.

 

따라서 다음과 같은 형태로 표현할 수 있다.

배열의 끝에는 1을 대입하고 나머지 요소들은 -1로 초기화한 후 배열의 끝부터 시작해 요소의 값이 -1이 아닌 요소들에 2를 곱한다. 이는 전체 수에 2를 곱하는 과정과 같다.

각 배열 요소는 자리의 수를 나타내야 하므로  arr[j] )의 값이 두 자리수라면  arr[j] 에는 

 arr[j] 를  10 으로 나눈 나머지를,  arr[j - 1] 에는  arr[j] 를  10 으로 나눈 몫을 넣는다. 단, 이 과정은 -1이 아닌 요소에 한해 수행한다. 여기서 -1은 초기화되지 않은 부분을 나타내므로 건드리면 안 된다.

BigInteger 클래스를 사용하면 더 빠르다.

import java.math.BigInteger;
 
public class Problem016 {
    private final static int N = 1000; 
 
    public static void main(String[] args) {
        System.out.println(run());
    }
 
    public static String run() {
        BigInteger num = new BigInteger("2");
        int result = 0;
        
        num = num.pow(N);
        
        while(!num.equals(BigInteger.ZERO)) {
            result += num.mod(BigInteger.TEN).intValue();
            num = num.divide(BigInteger.TEN);
        }
        
        return Integer.toString(result);
    }
 
}

실행 시간: 5ms = 0.005초