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

문제

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

프로그래머스

 

---

 

문제 개요

주어진 삼각형 구조에서 꼭대기에서 시작하여 대각선 아래 방향으로 이동하며 숫자의 합을 최대화하는 경로를 찾는 문제입니다. 각 위치에서는 바로 아래칸의 두 개의 숫자 중 하나로만 이동할 수 있습니다.

 

접근 방법

1. 역방향 동적 프로그래밍(DP)
   • 삼각형의 아래쪽에서부터 위쪽으로 값을 갱신하며 최대값을 계산합니다.
   • 각 칸에서 가질 수 있는 최대값을 그 칸의 값과 아래층 두 칸의 최대값 중 더 큰 값을 더하여 구합니다.
2. 구체적인 동작
   • 삼각형의 가장 아래층부터 시작하여 각 칸에서 바로 아래층의 두 칸 중 더 큰 값을 현재 칸에 더합니다.
   • 이를 반복하여 삼각형의 꼭대기까지 계산을 진행합니다.
   • 최종적으로 꼭대기 값은 최대 합 경로를 나타냅니다.

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for(int i=triangle.length-1; i>=1; i--) {
            for(int j=0; j<triangle[i].length-1; j++) {
                triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]);
            }
        }
        
        return triangle[0][0];
    }
}