(Java) Project Euler 018 - Maximum Path Sum I

// By starting at the top of the triangle below and moving to adjacent numbers on the row below,
// the maximum total from top to bottom is 23.

/*
                    3
                   7 4
                  2 4 6
                 8 5 9 3
*/

// 3 7 4 9 = 23

// Find the maximum total from top to bottom of the triangle below:

// NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route.
// However, Problem 67, is the same challenge with a triangle containing one-hundred rows;
// it cannot be solved by brute force, and requires a clever method!

 

import java.util.ArrayList;

public class ProjectEuler_018 {
    public static void main(String[] args) {
        ArrayList<int[]> Lines = new ArrayList<>();

        int maximumResult = Integer.MIN_VALUE;

        // 주어진 삼각형을 2차원 배열로 표현합니다.
        int[] Line_1 = {75};
        int[] Line_2 = {95, 64,};
        int[] Line_3 = {17, 47, 82};
        int[] Line_4 = {18, 35, 87, 10};
        int[] Line_5 = {20, 4, 82, 47, 65};
        int[] Line_6 = {19, 1, 23, 75, 3, 34};
        int[] Line_7 = {88, 2, 77, 73, 7, 63, 67};
        int[] Line_8 = {99, 65, 4, 28, 6, 16, 70, 92};
        int[] Line_9 = {41, 41, 26, 56, 83, 40, 80, 70, 33};
        int[] Line_10 = {41, 48, 72, 33, 47, 32, 37, 16, 94, 29};
        int[] Line_11 = {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14};
        int[] Line_12 = {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57};
        int[] Line_13 = {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48};
        int[] Line_14 = {63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31};
        int[] Line_15 = {4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23};

        Lines.add(Line_1);
        Lines.add(Line_2);
        Lines.add(Line_3);
        Lines.add(Line_4);
        Lines.add(Line_5);
        Lines.add(Line_6);
        Lines.add(Line_7);
        Lines.add(Line_8);
        Lines.add(Line_9);
        Lines.add(Line_10);
        Lines.add(Line_11);
        Lines.add(Line_12);
        Lines.add(Line_13);
        Lines.add(Line_14);
        Lines.add(Line_15);

        // 최대 합을 찾아 출력합니다.
        maximumResult = findMax(Lines);
        System.out.println("The maximum sum of this triangle is : " + maximumResult);
    }

    // 삼각형에서 가능한 최대 합을 찾는 메서드
    static int findMax(ArrayList<int[]> lines) {
        // 맨 아래에서부터 위로 올라가면서 각 위치의 최대 합을 계산합니다.
        for (int i = lines.size() - 2; i >= 0; i--) {
            for (int j = 0; j < lines.get(i).length; j++) {
                lines.get(i)[j] += Math.max(lines.get(i + 1)[j], lines.get(i + 1)[j + 1]);
            }
        }
        // 최종적으로 맨 꼭대기에 위치한 값이 가능한 최대 합입니다.
        return lines.get(0)[0];
    }
}

 

 

삼각형으로 생긴 배열에 대해

위에서부터 아래로의 경로 내의 수의 합이 가장 큰 값을 구하기

질문에서도 나와있지만, 삼각형의 층이 15층밖에 안되기 때문에, 총 경로는 16384개밖에 되지 않는다.

모든 경로에 대해 합을 구하는것도 하나의 방법이지만, 크기가 커지면 비효율적이다.

효율적인 계산을 위해서는 아래에서부터 값을 더해가는 방식으로, 각 위치에 대한 최대값을 계산하는 방식으로 해야한다.

무슨말인지 이해하기 어렵지만, 디버그를 하면서 배열을 하나씩 까보면 이해가 쉽다.

 

초기 삼각형 배열

 

맨 마지막 배열인 14번 배열은 그대로 두고, 13번째 배열에 대하여

 

i의 값을 변경시켜주는데, 13[i] = 14[i]와 14[i+1] 중 큰 값을 13[i]에 더한 값 으로 바꿔준다.

 

예를들어 13번 배열의 1번째 값이 63인데, 이 값은 다음 연산에 의해서 14번배열의 2번째 값인 62와 더해져서 125가 된다.

 

13번 배열 연산이 끝난 후.

 

이렇게 배열의 크기는 유지한채로, 위쪽으로 연산을 계속해 나가면

 

 

최종적으로는 가장 큰 값이 맨 위에 남게 된다.