[백준] 1932번: 정수 삼각형 - JAVA

🔗 문제 링크

BOJ 1932번: 정수 삼각형

1932번: 정수 삼각형

 

📝 풀이 과정

위층부터 차례로 누적하며 아래층으로 내려왔을 때, 가장 최대가 되는 수의 합을 구하는 문제이다.

문제대로 해결하는 방법도 있겠지만, 그렇게 되면 제일 마지막 층의 합을 구했을 때 다시 한 번 반복을 돌며 최대값을 찾아야 된다고 생각했다. 이를 반대로 아래에서 위로가며 최대값을 누적하는 방식으로 답을 구했다.

 

 

for (int i = N - 1; i > 0; i--) {
  for (int j = 0; j < i; j++)
    nums[i-1][j] += Math.max(nums[i][j], nums[i][j + 1]);
}

N - 1층부터 위로 올라가며 나와 내 오른쪽 칸 중 큰 값을 위의 칸에 더해주었다. 이렇게 계속 위로 더해가다보면 최종적으로 제일 상단에 있는 값은 아래칸부터 제일 큰 값들을 누적한 값이 더해지게 되므로 nums[0][0]의 값이 답이 된다.

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] nums = new int[N][];

        for (int i = 0; i < N; i++) {
            nums[i] = new int[i + 1];

            for (int j = 0; j <= i; j++)
                nums[i][j] = sc.nextInt();
        }

        for (int i = N - 1; i > 0; i--) {
            for (int j = 0; j < i; j++)
                nums[i-1][j] += Math.max(nums[i][j], nums[i][j + 1]);
        }

        System.out.println(nums[0][0]);

    }
}

 

📊 제출 결과