프로그래머스 Lv.3) 정수 삼각형 (DP)

정수 삼각형

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

 

풀이

 

DP를 푸는 방법 중 두 번 모두 bottom-up 방식으로 문제를 풀었다.

문제의 조건은, 삼각형 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 최대 값이 되는 것이다.

그래서 첫번째 풀었을 때는, 다른 분의 풀이를 보고 이해했던 것 같다.

 

첫번째 푼 방식은 위의 두 경로 중 최대 값을 같는 경로로 탐색하면서 마지막에 도착한 다음, 정렬을 통해 가장 큰 값을 리턴해주었다. 

 

두번째 푼 방식은, 이 경우, out of idx 방지를 신경써주지 않아도 되고, sort를 따로 해주지 않아도 된다는 생각에서 풀이 방법을 채택했다. 삼각형 가장 아래에 있는 경로 위에 점들부터 시작해서 위로 올라갈 때, 아래에 둘 중 더 큰 값을 가지고 올라왔다고 저장하면서 꼭대기 까지 올라갔다. 그 다음 꼭대기에 있는( 0,0 인덱스에 있는 ) 값을 리턴해주어 답을 구했다.

 

코드 1

 

import java.util.Arrays;

class Solution {
    static int max;
    
    public int solution(int[][] triangle) {
        int len = triangle.length;
        for(int depth =1; depth <len; depth++) {
            for(int idx=0; idx<triangle[depth].length; idx++) {
                int left = idx-1;
                int right = idx;
                if(left ==-1) {   // 0번 째 인덱스라는 말
                    triangle[depth][idx] += triangle[depth-1][idx];
                } else if(right == triangle[depth-1].length) {  // 마지막 인덱스
                    triangle[depth][idx] += triangle[depth-1][left];
                } else {    // 가운데 수들
                    triangle[depth][idx] += Math.max(triangle[depth-1][left], triangle[depth-1][right]);
                }
            }
        }
        
        Arrays.sort(triangle[len-1]);
        return triangle[len-1][len-1];
    }
}

 

코드 2

 

class Solution {
    public int solution(int[][] triangle) {
        for(int y= triangle.length-2; y>=0; y--) {
            for(int x=0; x<triangle[y].length; x++) {
                int left = x;
                int right = x+1;
                triangle[y][x] += Math.max(triangle[y+1][left], triangle[y+1][right]);
            }
        }
        return triangle[0][0];
    }
}