43105. 정수 삼각형

문제

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

제한사항

풀이

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int n = triangle.length;
        int[][] df = new int[n][n];
        
        for(int row = 0 ; row < n ; row ++) {
            int rowLen = row+1;
            for(int col = 0 ; col < rowLen ; col ++) {
                if(row == 0 && col==0) {
                    df[row][col] = triangle[row][col];
                    continue;
                }
                if(col == 0 ) {    
                    df[row][col] = df[row-1][col] + triangle[row][col];
                } else if (col == rowLen-1) {
                    df[row][col] = df[row-1][col-1] + triangle[row][col];
                    
                } else {
                    df[row][col] = Math.max(
                    df[row-1][col-1] + triangle[row][col],
                    df[row-1][col] + triangle[row][col]
                    );
                }
            }
            
            for(int i = 0 ; i < n ; i++) {
                answer = Math.max(df[n-1][i], answer);
            }
        }
        return answer;
    }
}

회고

비교적 쉬운 문제였다. 각 단계에서 최대의 이익을 위해 선택을 해야하는 문제였다. 그리디 알고리즘과 다이나믹 프로그래밍이 떠올랐다.

이진 트리 탐색을 하면서 리프 노드까지 합을 계산한다. 2가지 경우의 수를 고려했다. 양 끝에 노드가 있는 경우와 아닌 경우.

양 끝에 있으면 현재 노드와 직전 노드까지의 최대 총합을 더한 값이 현재 노드까지의 최대 총합일 것이다.

if(col == 0 ) {    
	// 왼쪽 끝
	df[row][col] = df[row-1][col] + triangle[row][col];
	} else if (col == rowLen-1) {
    //오른쪽 끝
    df[row][col] = df[row-1][col-1] + triangle[row][col];
    }

그 외 경우에는 각 노드에서 2가지 경우로 나뉜다. 현재 노드 직전까지 최대 총합은 2가지 경우가 있기 때문이다. 그래서 직전 경우의 수를 비교해서 큰 값과 현재 노드의 값을 합하면 그 값이 현재 노드까지의 최대 총합일 것이다.

else {
                    df[row][col] = Math.max(
                    df[row-1][col-1] + triangle[row][col],
                    df[row-1][col] + triangle[row][col]
                    );