[PG] 정수 삼각형 JAVA

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

삼각형 모양으로 쌓여있는 수를 나타낸 이차원 배열 int[][] triangle이 주어진다.

맨 위 꼭지점을 시작 위치로 하여 삼각형 밑면에 도착할 수 있는 여러가지 경로가 존재한다.

각 경로별로 길을 지나며 마주치는 숫자들을 더해나갔을 때 만들 수 있는 가장 큰 수를 반환해야한다.

 

단, 현재 위치에서 왼쪽 아래, 오른쪽 아래 둘 중 하나의 길로만 내려갈 수 있다. 올라가거나 옆으로 가는 경로는 존재하지 않는다.

 

 

풀이 .

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;

        // 초기화
        int[][] dp = new int[triangle.length][triangle.length];
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];  // 왼쪽 빗변 경로
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];  // 오른쪽 빗변 경로
        }

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

        // 마지막 행만 검사하면 된다
        for(int i = 0; i < triangle.length; i++) {
            if(answer < dp[triangle.length - 1][i]) {
                answer = dp[triangle.length - 1][i];
            }
        }
        return answer;
    }
}

전형적인 DP문제이다. 브루트 포스로 풀려면 n중 for문을 사용해야 하는데 n은 최대 500이다. 무조건 시간초과.

 

dp[i][j] 는 [i][j] 까지 도착할 수 있는 모든 경로들 중 최대값을 저장하도록 한다.

 

주어진 그림은 정삼각형이지만 2차원 배열의 행들을 그대로 나열해보면 직각삼각형이 된다.

이 형태에서 힌트를 얻어 초기화를 할 수 있다.

 

정삼각형이라고 봤을 때 양 옆 빗면을 그대로 따라가는 경로 2가지를 dp를 돌리기 전에 바로 구할 수 있게 된다.

그 후 2중 for문을 통해 dp를 돌렸다.

이때 for ( int j ) 의 범위를 ( j < triangle.length ) 로 잡아도 잘 돌아가긴 하지만 그래도 최대한 시간을 단축시켜보려고    ( j < i ) 로 잡았다.

 

이제 모든 경로의 도착지점인 마지막 행의 열들을 검사하여 최대값을 알아낼 수 있다.