[BOJ] 백준 [1932] 정수 삼각형 JAVA

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

1932번: 정수 삼각형

 

문제

풀이

밑으로 진행 할 수록 , 최대한 값이 높게 나오게 합산하면서 내려오는 방식이다.

예제 입력처럼 주어진다면 "바로 위" 혹은 "왼쪽 위" 에서 값을 받아 내려올 수 있으므로

점화식은 => arr[i][j] = arr[i][j] + Math.max(arr[i-1][j],arr[i-1][j-1]); 이다.

 

하지만 왼쪽끝이나 오른쪽 끝에서는 둘 중에 큰 값을 받는것 대신 하나만 선택할 수 있으므로 그 조건만 추가하면 된다.

 

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n+1][n+1];
 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                arr[i][j] = sc.nextInt();
                if(j==1)
                    arr[i][j] = arr[i][j] + arr[i-1][j];
                else if(j==i)
                    arr[i][j] = arr[i][j] + arr[i-1][j-1];
                else
                    arr[i][j] = arr[i][j] + Math.max(arr[i-1][j],arr[i-1][j-1]);
            }
        }
        Arrays.stream(arr[n]).max().ifPresent(System.out::println);
    }
}