EunSung.log

정수 삼각형

3 min read

문제 정보

풀이

현재 단계에서 최적인 값을 알 수 없고, 현재 선택한 값이 이후 선택 가능한 값의 범위에 영향(현재에서 대각선 왼쪽이나 오른쪽만 가능)을 미치기 때문에, DP를 사용하는 문제다.

dp 배열을 다음과 같이 정의한다.

  • dp[i][j]: i 단계의 j번째 원소에 도착했을 때의 최대값.

그렇기에 점화식은 dp[i][j] = triangle[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])가 된다. 다만 대각선 왼쪽이나 오른쪽이 없는 왼쪽 끝이나 오른쪽 끝은 따로 처리해줘야 한다.

피보나치 수를 구할 때나 20260203 RGB 거리처럼, 현재 단계의 값을 구할 때 이전 행의 값만 필요하다. 그렇기에 이전 행 전체를 저장할 필요 없이 1차원 배열을 재사용하는 방식으로 공간을 최적화할 수 있다.

이때, j를 역순(오른쪽 → 왼쪽)으로 순회해야 한다는 점을 주의해야 한다.

순방향으로 순회할 경우, dp[j-1]이 이미 현재 행의 값으로 덮어써진 상태가 되어 이전 행의 값을 참조할 수 없게 된다. 역순으로 순회하면 dp[j-1]이 아직 이전 행의 값을 유지하고 있으므로 올바르게 참조할 수 있다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int j = i; j >= 1; j--) {
                int element = Integer.parseInt(st.nextToken());
                
                if (j == 1) {
                    dp[j] = element + dp[j];
                    continue;
                }
                
                dp[j] = element + Math.max(dp[j - 1], dp[j]);
            }
        }
                
        int answer = 0;
        for (int i = 1; i <= n; i++)
            answer = Math.max(answer, dp[i]);
        
        System.out.println(answer);
    }
}

백링크