프로그래머스 LEVEL 3 : 정수 삼각형 (DP)

프로그래머스 LEVEL 3 : 정수 삼각형

언어 : JAVA

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

---

풀이

핵심

위에서 부터 나올 수 있는 경우의 수 중 최대값을 비교해서 복사된 배열에 수를 각각 누적해 준다.

그러면 맨 마지막배열에 나온 수들이 각각의 최대값들을 저장하게 되므로

맨 마지막 배열의 값 중 MAX 값을 찾으면 문제가 풀린다.

상세 풀이

위 그림은 피라미드 모양으로 되어있지만 사실 2차원 배열에 넣는 것이기 때문에 실제 데이터는 다음과 같이 들어간다.

 

먼저, 숫자를 누적시킬 배열을 만들어 준다.

크기는 triangle 배열과 같은 크기다.

int[][] copyTriangle = new int[triangle.length][triangle.length];

 

그림에서 볼 수 있듯이 피라미드의 좌, 우 끝은 해당 수만 올 수 있으므로 경우의 수가 1이다.

따라서 각각을 누적시켜 copyTriangle 배열에 넣어준다.

copyTriangle[0][0] = triangle[0][0]; // 맨 꼭대기 값을 넣어준다.
for (int i = 1; i < triangle.length; i++) {
    copyTriangle[i][0] = copyTriangle[i - 1][0] + triangle[i][0]; // 왼쪽 끝 값
    copyTriangle[i][i] = copyTriangle[i - 1][i - 1] + triangle[i][i]; // 오른쪽 끝 값
}

그러면 아래와 같이 배열에 값이 들어가 있는 상태가 된다.

7  0  0 0 0 
10 15 0 0 0 
18 0 15 0 0 
20 0 0 19 0 
24 0 0 0 24 

 

이제 위에서 부터 수를 비교해서 최대값을 copyTriangle에 넣어주면 끝이다.

for (int i = 2; i < triangle.length; i++) {
    for (int j = 1; j < i; j++) {
        copyTriangle[i][j] = Math.max(copyTriangle[i - 1][j - 1], copyTriangle[i - 1][j]) 
            + triangle[i][j];
    }
}

 

그 후 다시 배열을 살펴보자.

7   0  0  0  0 
10 15  0  0  0 
18 16 15  0  0 
20 25 20 19  0 
24 30 27 26 24 

여기에서 맨 마지막 배열의 값들이 바로 해당 경로의 최대값 들이다.

24 30 27 26 24 

이 경로들 중 MAX값을 구하면 그 값이 모든 경우의 수의 최대값이 된다.

MAX값은 다음과 같이 쉽게 구할 수 있다.

int maxNo = copyTriangle[copyTriangle.length - 1][0];
for (int i = 1; i < triangle.length; i++) {
    int checkNo = copyTriangle[copyTriangle.length - 1][i];
    if (maxNo < checkNo) {
        maxNo = checkNo;
    }
}

이처럼 이전 값들을 활용하는 DP로 문제를 쉽게 풀 수 있었다.

전체 코드

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] triangle = new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        System.out.println(solution.solution(triangle));
    }
}

class Solution {
    public int solution(int[][] triangle) {
        int[][] copyTriangle = new int[triangle.length][triangle.length];

        copyTriangle[0][0] = triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            copyTriangle[i][0] = copyTriangle[i - 1][0] + triangle[i][0];
            copyTriangle[i][i] = copyTriangle[i - 1][i - 1] + triangle[i][i];
        }

        for (int i = 2; i < triangle.length; i++) {
            for (int j = 1; j < i; j++) {
                copyTriangle[i][j] = Math.max(copyTriangle[i - 1][j - 1], copyTriangle[i - 1][j])
                    + triangle[i][j];
            }
        }

        int maxNo = copyTriangle[copyTriangle.length - 1][0];
        for (int i = 1; i < triangle.length; i++) {
            int checkNo = copyTriangle[copyTriangle.length - 1][i];
            if (maxNo < checkNo) {
                maxNo = checkNo;
            }
        }
        return maxNo;
    }
}