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

문제 힌트

1. 문제 이해:
   • 주어진 삼각형의 맨 위에서 시작하여 아래로 내려가면서 합이 최대가 되는 경로를 찾아야 합니다.
   • 각 경로의 합은 이동 경로의 숫자를 모두 더한 값입니다.
2. 동적 계획법 적용:
   • 동적 계획법을 사용하여 부분 문제를 해결함으로써 전체 문제를 해결합니다.
   • 여기서는 각 경로의 최대 합을 구할 때, 이전 단계의 계산 결과를 이용합니다.
3. bottom-up 접근:
   • 삼각형의 맨 아래에서부터 시작하여 위로 올라가면서 각 위치에서의 최대 합을 계산합니다.
   • 이 접근 방식은 각 단계에서 최적 부분 구조를 활용할 수 있도록 합니다.

 

---

정답은 더보기 클릭

class Solution {
    
    public int solution(int[][] triangle) {
        // 동적 계획법을 위한 bottom-up 방식 사용
        
        // 삼각형의 맨 아래에서부터 위로 올라가면서 계산
        for (int i = triangle.length - 1; i > 0; 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];
    }
}