Backjoon(백준) 1932번 - 정수삼각형(Java)

1. 풀이 과정

 - 각 층의 숫자마다 윗 층부터 조건에 맞게 내려온 숫자들의 최대합을 구하여 저장한뒤 각 합 중에서 최대 값을 판별한다.

 

* 풀이 과정 예시

 1) 각 층의 양 끝 숫자의 합은 윗 층 부터 대각선으로 한 방향으로 내려온 숫자들의 합이 최대 합이된다.

 2) 각 층의 양 끝값 사이의 수들은 윗 층으로 부터 내려온 숫자중에서 현재 층의 숫자의 앞으로 한칸 뒤로 한칸 값의 합이 된다.

 3) 또한 양 끝값 사이의 수가 둘 이상일 경우 다음 층으로 내려가기 전에 각 숫자들의 합중에 최대 값을 구한 뒤 다음 층을 계산한다.

 4) 위와 같이 각 층의 숫자들의 최대합을 구하면서 마지막 층으로 내려가면 최종적으로 왼쪽 끝값, 오른쪽 끝값, 가운데 값이 남게 된다.

 5) 마지막으로 남은 세 값의 최대값이 정답이다.

 

2. 코드 구현

 - 삼각형에 들어갈 값을 입력한 그 자리에 바로 계산한 최대합을 저장한다.

 - 각 삼각형의 위치에 바로 최대합을 저장해서, 계산할 때 입력받은 삼각형의 값이 아닌 최대합끼리 계산할 수 있도록 코드를 구현한다.

 - 최대합의 저장은 현재 삼각형에 있는 수 + 이전 위치에서 최대값.

 

import java.util.Scanner;

public class IntegerTriangle {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int max = 0, n = sc.nextInt();
        int[][] dp = new int[501][501];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = sc.nextInt(); // 각 층에 숫자 입력
                
                // 숫자 입력과 동시에 최대값 판별 
                if (j == 1) {
                    dp[i][j] += dp[i - 1][j]; //양 끝값은 그대로 내려온 값이 최대합
                } else if (j == i) {
                    dp[i][j] += dp[i - 1][j - 1];
                } else {
                    dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]); // 중간에 있는 수 최대합 판별
                }
                // 최대값 저장
                max = Math.max(max, dp[i][j]);
            }
        }
        System.out.println(max);
        
        sc.close();

    }

}

 

* Buffer로 입력받아서 구현해보기