[JAVA] 프로그래머스 : 정수 삼각형 (코딩테스트 고득점 kit > 동적계획법(Dynamic Programming))

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

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

동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함

이 과정을 통해 점화식을 세우는게 중요함

그리고 메모제이션을 해서 시간을 줄이는게 중요함
=>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로

메모제이션 방법으로는 아래와 같은 방법이 있음 
1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법 (BOTTOM-UP)
2. 그 순간 필요하면 계산해서 저장하는 방법(TOP-DOWN)

 

해결 방안

1. 삼각형의 왼쪽, 오른쪽, 가운데를 나눠서 생각함. 왼쪽 오른쪽은 계속 누적이고 가운데는 위의 숫자 중 더 큰 것을 저장해주면 됨(점화식은 코드참고)
=> 메모제이션 방법으로 BOTTOM-UP을 사용함

2. 가장 밑부분일때 가장 큰 값을 answer에 저장해줌 

 

코드

// 정수 삼각형
class Solution {
    
    public int solution(int[][] triangle) {
        int answer = 0;

        /*
        7             7
        3 8           10 15
        8 1 0         18 16 15
        2 7 4 4       20 25 20 19
        4 5 2 6 5     24 30 27 26 24
        */
        int[][] sum = new int[triangle.length][];
        int temp1, temp2;
        for(int i=0; i<sum.length; i++){
            
            sum[i] = new int[triangle[i].length];
            if(i==0){
                sum[0][0] = triangle[0][0];
                System.out.println(sum[0][0]);
                continue;
            } 
                
            for(int j=0; j<sum[i].length; j++){
                // 왼쪽
                if(j==0){
                    sum[i][j] = sum[i-1][j] + triangle[i][j];
                }
                // 오른쪽
                else if(j==sum[i].length-1){
                    sum[i][j] = sum[i-1][sum[i-1].length-1] + triangle[i][j];
                }
                // 가운데
                else{
                    temp1 = sum[i-1][j-1] + triangle[i][j];
                    temp2 = sum[i-1][j] + triangle[i][j];
                    sum[i][j] = Math.max(temp1, temp2);
                }
                //System.out.print(sum[i][j] + " ");
                
                // 최댓값 구해주기
                if(i==sum.length-1){
                    answer = Math.max(answer, sum[i][j]);
                }
            }
            //System.out.println();            
        }

        return answer;
    }
}