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

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

 

 

처음에는 dfs를 이용해서 문제를 해결했지만, 답은 맞게 나오나 시간초과가 발생하였다.

 

때문에 중복 계산을 방지하기 위해 메모이제이션 기법을 사용해야 한다.

 

메모이제이션 : 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지

 

<정답 코드>

import java.util.*;

class Solution {
     int[][] dp;
    int answer = 0;
    public int solution(int[][] triangle) {
        dp = new int[triangle.length][triangle.length];
        for(int[] row : dp){
            Arrays.fill(row,-1); //dp배열을 -1로 초기화
        }
        return dfs(triangle,0,0);
    }
    
    public int dfs(int[][] triangle, int h, int w){
       
        if(h==triangle.length-1){
            return triangle[h][w];
        }
        if(dp[h][w]!=-1){ //현재 위치의 최대값이 저장 되어 있으므로 중복 계산 방지, 더 내려갈 필요 없다.
            return dp[h][w];
        }
        int left = dfs(triangle,h+1,w);
        int right = dfs(triangle,h+1,w+1);
        
       return dp[h][w] = triangle[h][w]+Math.max(left,right);
    }
}

 

최대값을 아래서 위부터 구한다.

 

여기서 가장 중요한건 dp배열에 현재 위치에서 아래로 내려갈때 가장 최대값을 저장하여 중복 계산을 방지했다는 점이다.

 

왼쪽으로 가는 경우와 오른쪽으로 가는 경우중 최대값을 반환한다.