문제

[프로그래머스] 정수 삼각형
https://school.programmers.co.kr/learn/courses/30/lessons/43105

풀이

조건

• 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾습니다.
  아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.

풀이 순서

• DP를 사용한다.
• 삼각형의 위치별로 최대값을 저장할 배열을 생성한다.
• 삼각형의 가장 왼쪽은 미리 누적합을 구한다.
  • 배열로 표현했을 때 가장 왼쪽의 값은 바로 위에서 더해 내려오는 값이 최대값이기 때문이다.
• 구한 점화식대로 구현한다.
  • 왼쪽 위에서 내려와 더했을 때
    • dp[i-1][j-1] + triangle[i][j]
  • 오른쪽 위에서 내려와 더했을 때
    • dp[i-1][j] + triangle[i][j]
• 삼각형의 가장 아래쪽에서 가장 큰 값을 구하면 답을 구할 수 있다.

코드

Java

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int height = triangle.length; // 삼각형 높이
        
        int[][] dp = new int[height][height]; // 합 기록할 배열
        
        // 가장 왼쪽 단계는 미리 저장
        dp[0][0] = triangle[0][0];
        for(int i = 1; i < height; i++) {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
        }
        
        // 위에서부터 높이 하나씩 내려가면서 최대값 구하기
        for(int i = 1; i < height; i++) {
            for(int j = 1; j < triangle[i].length; j++) {
            	// 왼쪽 위에서 내려와 더했을 때, 오른쪽 위에서 내려와 더했을 때 중 최대값 저장
                dp[i][j] = Math.max(dp[i-1][j-1] + triangle[i][j], dp[i-1][j] + triangle[i][j]);
            }
        }
        
        // 삼각형의 바닥에서 가장 큰 값 구하기
        for(int i = 0; i < height; i++) {
            answer = Math.max(dp[height - 1][i], answer);
        }
        
        return answer;
    }
}

정리

• 전형적인 DP 문제여서 쉬웠다.