[Project Euler] Problem 018

public class Problem018 {
 
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static String run() {
        int[][] arr = {
                {75},
                {95, 64},
                {17, 47, 82},
                {18, 35, 87, 10},
                {20,  4, 82, 47, 65},
                {19,  1, 23, 75,  3, 34},
                {88,  2, 77, 73,  7, 63, 67},
                {99, 65,  4, 28,  6, 16, 70, 92},
                {41, 41, 26, 56, 83, 40, 80, 70, 33},
                {41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
                {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
                {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
                {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
                {63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
                { 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23}
        };
        
        for(int i = (arr.length - 2); i >= 0; --i) {
            for(int j = 0; j < arr[i].length; ++j) {
                arr[i][j] += Math.max(arr[i + 1][j], arr[i + 1][j + 1]);
            }
        }
        
        return Integer.toString(arr[0][0]);
    }
}

정답: 1074

실행 시간: 300000ns = 0.0003초 

위에서 아래로 찾아가는 방식이 아니라, 아래에서부터 위로 경로를 찾는 방식이다.

처음에는 위에서 아래로 하려고 했는데, 그런 식으로 16384개의 경로를 찾는다는 건 좀 아닌 것 같아서 거꾸로 찾기로 했다.

밑에서 두 번째 행에서부터 시작해 각 요소들에 그 요소의 밑에 있는 두 값 중 큰 값을 더한다.

63에는 4, 62 중 62를, 66에는 62, 98 중 98를 더하고, … 이 과정을 반복하면 경로가 완성된다.

맨 끝부터 시작해 최대 합을 갖는 경로를 유도해나가는 것이다. 

결국  arr[0][0] 에는 최대 합이 저장된다.