[프로그래머스]정수 삼각형 - Java

문제

https://programmers.co.kr/learn/courses/30/lessons/43105?language=java

 

 

풀이

DP 문제임. DP 문제는 보면 뭔가 DP 문제 같은데 어케 푸는지 모르는 경우가 허다한 것 같음 ㅠ

근데 오랜만에 맞춰서 좀 좋았음 ㅎㅎㅎㅎㅎ

 

삼각형의 위에서 부터 내려오면서 더해주는게 아니라 새로운 2차원 배열을 만들어서 거꾸로, 그니까 밑에서 부터 올라가면서 비교하면서 새로운 배열에 최대값을 저장해주는 식으로 풀었음!

 

어떻게 푸는지 떠올리기만 하면 쉽게 풀리는게 DP의 매력아닌 매력인 것 같음!

 

 

코드

// 코딩테스트 연습 - 동적계획법 - 정수 삼각형
// https://programmers.co.kr/learn/courses/30/lessons/43105?language=java

package PROGRAMMERS;

public class IntegerTriangle {
    private static class Solution {
        private int solution(int[][] triangle) {
            int[][] arr = new int[triangle.length][triangle.length];

            // 맨 밑줄 채워주기
            for (int i = 0; i < triangle.length; i++) {
                arr[arr.length - 1][i] = triangle[triangle.length - 1][i];
            }

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

            return arr[0][0];
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(sol.solution(new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}}));
    }
}