[java] 프로그래머스 : 정수 삼각형

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

프로그래머스

풀이 접근법 : DP 메모이제이션 방법으로 위에서부터 아래로 가면서 좌,우의 큰 값과 해당 위치에 triangle[x][y]를 더해줘 가장 마지막 줄에 맥스값을 리턴해준다.

 

package programmers;

public class lesson_43105 {

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

    static class Solution {
        static int[][] dp;
        public int solution(int[][] triangle) {
            int answer = 0;
            int num = triangle[triangle.length - 1].length;
            dp = new int[num][num];
            int max = Integer.MIN_VALUE;

            for(int i = 0; i<num; i++){
                max = Math.max(triDp(triangle,triangle.length - 1, i, triangle.length - 1), max);
            }

            for (int i = 0; i <5; i++) {
                for (int j = 0; j < 5; j++) {
                    System.out.print(dp[i][j] + " ");
                }
                System.out.println();
            }

            return max;
        }
        public int triDp(int[][] triangle,int x,int y, int depth){

            if(depth == 0){
                return triangle[0][0];
            }

            if(dp[x][y] != 0){
                return dp[x][y];
            }

            int nextX = x >= 1 ? x-1 : 0;
            int nextY = y >= 1 ? y-1 : 0;
            if( y >= triangle[x].length - 1){
                y = triangle[x].length - 1;
            }

            if(y == 0){
                dp[x][y] = triDp(triangle,nextX,0,depth -1) + triangle[x][y];
            }else if(y == triangle[x].length -1){
                dp[x][y] = triDp(triangle,nextX,y,depth - 1) + triangle[x][y];
            }else{
                dp[x][y] = Math.max(triDp(triangle,nextX,nextY,depth -1),triDp(triangle,nextX,y,depth - 1)) + triangle[x][y];
            }

            return dp[x][y];
        }
    }
}

나는 메모이제이션 방식으로 풀었지만, 다른 사람의 풀이 중 타뷸레이션 방식(아래에서 위로) 간략하게 코드를 작성한 게 있어 가져와 보았다. 

 

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        for (int i = 1; i < triangle.length; i++) {
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for (int j = 1; j < i; j++) 
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
        }

        return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
    }
}

triangle 배열은 삼각형 모양의 배열로 양 끝에 대한 값은 triangle[i][0] , triangle[i][i] 로 기존 값에 삼각형의 상위 값을 더해주고, 양 끝단의 사잇값은 아래 쪽에 for문으로 하나씩 채워주고 있다. 정말 직관적이다. ( 다른 사람의 풀이에는 못 미치지만 어떻게든 DP로 된 문제를 내 손으로 풀어 뿌듯하다.)