정수 삼각형

문제정의

---

삼각형의 꼭대기부터 바닥까지 가는 경로 중에서 경로의 합이 가장 큰 것을 찾는 문제이다. 아래쪽으로 갈 때는 자신의 바로 왼쪽 아래나 오른쪽 아래로만 이동할 수 있다.

문제풀이

---

전체 코드는 다음과 같다.

public class IntegerTriangle {

    //프로그래머스 문제풀이 level3 정수 삼각형
    public static void main(String[] args) {
        int[][] triangle = {
            {7},
            {3,8},
            {8,1,0},
            {2,7,4,4},
            {4,5,2,6,5}
        };

        int answer = 0;
        int[][] sum = new int[triangle.length][triangle.length];
        int len = 2;
        
        if(triangle.length == 1)
            System.out.println(triangle[0][0]);
        
        sum[0][0] = triangle[0][0];
        for(int i = 1; i < triangle.length; i++)
        {
            sum[i][0] = triangle[i][0] + sum[i-1][0];
            sum[i][len-1] = triangle[i][len-1] + sum[i-1][len-2];
            for(int j = 1; j < len-1; j++)
            {
                int max = Math.max(sum[i-1][j-1], sum[i-1][j]);
                sum[i][j] = max + triangle[i][j];
            }
            len++;
        }
        len--;
        for(int i = 0; i < len; i++)
            answer = Math.max(answer, sum[triangle.length-1][i]);
        System.out.println(answer);
    }
    
}

아이디어는 이렇다. 삼각형의 밑변을 길이로 하여 2차원 배열을 생성한다. 그리고 여기에 해당 위치에 오기까지의 합 중 가장 큰 것을 넣을 것이다. 필자는 이를 sum이라 하였다. sum[0][0]은 맨 꼭대기이므로 triangle[0][0]을 넣는다. 꼭대기에서 갈 수 있는 곳은 3과 8이다. 3의 위치에서 최대값은 3+7=10, 8위치에서 합의 최대는 7+8=15이다. 3번째 줄로 내려가보자. 8은 3의 위치에서 내려올 수 밖에 없으므로 최대값은 10+8=18이다. 1의 경우 2번째 줄의 3과 8에서 둘 다 내려올 수 있다. 이 문제는 최대를 찾는 문제이므로 10과 15중 15를 선택하여 15+1=16을 기록하면 된다.

이런식으로 sum을 채워나가고 가장 아래층의 수 중 가장 큰 수를 찾으면 된다. 이를 코드로 그대로 구현하였다. sum을 정사각형으로 선언했기 때문에 각 층에 있는 숫자의 개수를 len으로 알려주었다. 가장 꼭대기를 채워넣고 그 아래부터는 for문의 영향을 받는다. 각 층에서 맨 왼쪽과 오른쪽 원소는 내려오는 경로가 하나밖에 없기 때문에 이는 따로 처리한다. 이를 제외한 원소는 위층의 왼쪽 대각선과 오른쪽 대각선의 sum값을 비교 한뒤 큰 값을 취한다. 각 층에서의 연산이 끝나면 len을 증가한다.

반복이 끝나면 맨 아래층의 원소에서 최대값을 찾아 반환한다.

연산 횟수는 삼각형의 밑변을 n이라 할 때, \(n^2 \over 2\)이므로, 최종 시간복잡도는 \(O(n^2)\)이다.

테스트

다이나믹 프로그래밍에 약한 편이다. 이건 기초문제라 쉽게 해결했지만, 이 유형에 좀 더 익숙해져야겠다.