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

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

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

<예제 이미지>

 

대표적인 동적계획법 문제 같았다

 

항상 좌우 양끝은 내려올 수 있는 경로가 정해져 있었고

꼭대기를 기준으로 내려가며 더할때마다 올수있는 경로중 최대값을 위치에 저장한다면 불필요한 연산을 줄일 수 있다.

 

입력 :

[7]

[3, 8]

[8, 1, 0]

[2, 7, 4, 4]

[4, 5, 2, 6, 5]

 

입력은 위와같이 주어지며 왼쪽대각선을 갈때는 y++, 오른쪽 대각선을 갈때는 x++ y++ 와같은 방법으로 이동시켰다

 

class Solution {
    private static int[][] nodes;
    private static int[][] nodesSum;
    public int solution(int[][] triangle) {
        nodes = triangle;
        nodesSum = new int[triangle.length][triangle.length];
        return DP(0,0);
    }
    
    public int DP(int x,int y){
        if(y==nodes.length){return 0;}
        if(nodesSum[y][x]>0){return nodesSum[y][x];}
        return nodesSum[y][x] = nodes[y][x] + Math.max(DP(x,y+1),DP(x+1,y+1));
    }
}