99클럽 코테 스터디 19일차 TIL - DP (프로그래머스 '정수 삼각형')

항해99 코테 스터디 19일차 문제인 프로그래머스의 '정수 삼각형'은 정수로 이루어진 삼각형을 한층씩 타고 내려가면서 맨 밑층까지 도달했을 때 구할 수 있는 가장 큰 합을 구하는 문제다. 난이도는 레벨3이며 동적계획법을 통해 해결할 수 있다.

 

오늘의 문제 - 정수 삼각형 문제 정보

문제 키워드

- DP

난이도

- Level 3

 

문제 요약

• 한변의 길이가 N인, 정삼각형 모양의 배열이 주어진다. 각 원소의 값은 모두 0 이상의 9999 이하의 정수이다.
• 맨 윗칸에서 한칸씩 아래로 내려가며 합을 구해가는데, 아래로 내려갈 때는 바로 왼쪽 대각선 또는 오른쪽 대각선으로만 이동할 수 있다. 이렇게 맨 밑층까지 내려갔을 때 구해진 합들 중 최대값을 구하여라.

 

문제 풀이 과정  

• 이전까지의 합을 이용해 다음 합을 구할 수 있는, 정석적인 DP 문제이다.
• 위에서부터 아래로 가며 합을 구한 뒤 최댓값을 찾을 수도 있지만, 반대로 아래에서부터 더 큰값만 올리면 맨 꼭대기에 최댓값이 남게되므로 이 방식을 사용했다.
• dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]

코드

class Solution {
    public int solution(int[][] triangle) {
        int N = triangle.length;
        int[][] dp = new int[N][N];
        
        // 맨 밑층의 값으로 초기화
        for(int i=0; i<N; i++) {
            dp[N-1][i] = triangle[N-1][i];
        }
        
        // 한 층씩 올라오며, 왼쪽아래와 오른쪽아래의 현재까지의 합 중 더 큰 값을 가지고 이번 합 계산
        for(int depth = N-2; depth >= 0; depth--) {
            for(int i=0; i<=depth; i++) {
                int nowValue = triangle[depth][i];
                dp[depth][i] = Integer.max(dp[depth+1][i], dp[depth+1][i+1]) + nowValue;
            }
        }
        
        // 꼭대기 층에 계산된 합을 정답으로 반환
        return dp[0][0];
    }
}

• 시간복잡도: O(N^2) → N: 삼각형의 높이
• 공간복잡도: O(N^2)