[프로그래머스/Java] Lv.3 - 정수삼각형

승래·2026년 1월 29일

Lv.3 - 정수삼각형

1. 문제 요구사항

입력: 삼각형 모양으로 배치된 정수 배열 triangle (꼭대기부터 바닥까지 이어짐).
이동 규칙: 현재 위치에서 한 칸 아래로 이동할 때, 대각선 왼쪽([i+1][j]) 또는 대각선 오른쪽([i+1][j+1])으로만 이동 가능하다.
목표: 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐 간 숫자의 합이 가장 큰 경우를 찾아 그 합을 반환한다.
제한: 삼각형의 높이는 최대 500이다.

2. 접근 방식 (Algorithm)

이 문제는 전형적인 동적계획법(Dynamic Programming) 문제다.
위에서부터 아래로 내려가며 합을 구하되, 특정 위치 (i, j)에 도달했을 때의 최댓값은 "바로 위층에서 올 수 있는 두 경로 중 더 큰 값을 선택"하는 것으로 결정된다.

1) DP 테이블 정의

dp[i][j]: (0, 0)에서 시작해 (i, j) 위치까지 도달했을 때 얻을 수 있는 최대 합.
메모리 효율을 위해 2차원 배열을 선언하되, 삼각형 모양에 맞춰 가변 배열(Jagged Array) 형태로 초기화했다.

2) 점화식 도출

현재 위치 (i, j)로 내려올 수 있는 경우는 위층(i-1)의 두 곳이다.

왼쪽 대각선 위: (i-1, j-1)
오른쪽 대각선 위: (i-1, j)

따라서 기본 점화식은 다음과 같다.
$dp[i][j] = triangle[i][j] + \max(dp[i-1][j-1], dp[i-1][j])$

3) 경계값(Edge Case) 처리

하지만 단순히 위 점화식만 쓰면 인덱스 에러(ArrayIndexOutOfBounds)가 발생한다. 삼각형의 양쪽 끝은 내려올 수 있는 경로가 하나뿐이기 때문이다.

왼쪽 끝 (j == 0): 바로 위층의 0번 인덱스에서만 올 수 있다.
- dp[i][j] = triangle[i][j] + dp[i-1][j]
오른쪽 끝 (j == len-1): 바로 위층의 마지막 인덱스에서만 올 수 있다.
- dp[i][j] = triangle[i][j] + dp[i-1][j-1]
그 외 가운데: 위층의 두 값 중 큰 값을 선택한다.

3. 코드

import java.util.*;

// dp[i][j] = triangle[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);

public class Solution {
    public static int solution(int[][] triangle){
        int answer = 0;
        int n = triangle.length; // size
        int[][] dp = new int[n][];
        
        for(int i=0; i<n; i++) {
            dp[i] = new int[i+1];
        }
        
        dp[0][0] = triangle[0][0];
        
        for(int i=1; i<n; i++) {
            for(int j=0; j<triangle[i].length; j++) {
                if(j == 0) {
                    dp[i][j] = triangle[i][j] + dp[i-1][j];
                }
                else if(j == triangle[i].length - 1) {
                    dp[i][j] = triangle[i][j] + dp[i-1][j-1];
                }
                else {
                    dp[i][j] = triangle[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);   
                }
            }
        }
        
        for(int maxVal : dp[n-1]) {
            answer = Math.max(answer, maxVal);    
        }
        
        return answer;
    }
}

4. 느낀점 & 배운점

1. DP에 대한 자신감 회복

어제까지만 해도 실버 난이도의 DP 문제도 접근조차 못 해서 우울했는데, '계단 오르기'를 통해 "현재 값을 구하기 위해 과거의 값을 참조한다"는 DP의 본질을 이해하고 나니 Lv.3 문제도 두렵지 않게 되었다. 역시 기본기가 중요하다.

2. 가변 배열 (Jagged Array) 활용

자바에서 2차원 배열의 열 크기를 행마다 다르게 설정할 수 있다는 점을 활용했다.
new int[n][]으로 선언하고, 반복문을 돌며 new int[i+1]로 할당하니 삼각형 구조에 딱 맞는 배열이 만들어져서 인덱스 관리하기도 편하고 메모리도 절약할 수 있었다.

3. 꼼꼼한 인덱스 처리

DP 문제는 점화식도 중요하지만, j-1 같은 인덱스를 참조할 때 범위 밖으로 나가는 것을 방지하는 것이 핵심이다. 이번에는 if (j==0), else if (j==last), else로 명확하게 분기 처리를 해서 한 번에 정답 처리를 받을 수 있었다.

Tags: #Java #Algorithm #Programmers #DP #DynamicProgramming