[백준]1932번 정수 삼각형(java)

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

1932번 정수 삼각형 문제 링크입니다.

 

핵심

이번 문제도 동적 계획법 문제이다. 위에서부터 숫자가 내려가며 합해지는데, 대각선으로 갈 수 있다. 이중 배열을 사용하여 줄의 위치는 앞에 각 값은 뒤에 넣는다.

정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n+1][n+1];
        for (int i=1; i < n+1; i++){
            for (int j = 1; j<i+1; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        int max = 0;
        for (int i =1; i <n+1; i++) {
            for (int j = 1; j < i + 1; j++) {
                arr[i][j] += Math.max(arr[i-1][j-1],arr[i-1][j]);
                if (i ==n){
                    max = Math.max(max,arr[i][j]);
                }
            }
        }
        System.out.println(max);
    }
}

해설

저번 RGB거리 문제와 매우 유사하다. 내려가면서 합을 저장해주는 방식을 사용하였다.

이중 배열을 선언한다. arr[i][j] 에서 i는 줄의 위치이다. j는 그 줄의 값 순서이다.

숫자가 아래로 내려갈때, 대각선으로만 움직일 수 있다.

즉 arr[i][j] 는 arr [i-1][j-1]의 값을 더하거나, arr [i-1][j]의 값이 더해진다.

최댓값을 저장해준다.

i==n일 때, 맨 마지막 줄일 때, 각 값에 더해진 값 중 가장 큰 값을 구한다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.