[JAVA] 백준 1932번: 정수 삼각형 ( 초급 1 - 28 )

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class baekjoon1932_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<ArrayList<Integer>> info = new ArrayList<>();

        info.add(new ArrayList<>());
        info.get(0).add(sc.nextInt());

        for (int i = 1; i < n; i++) {
            info.add(new ArrayList<>());
            for (int j = 0; j < i + 1; j++) {
                info.get(i).add(sc.nextInt());
                // 맨 왼쪽에 있는 case
                if (j == 0) {
                    info.get(i).set(j, info.get(i - 1).get(j) + info.get(i).get(j));
                    continue;
                }
                // 맨 오른쪽에 있는 case
                if (j == i) {
                    info.get(i).set(j, info.get(i - 1).get(j - 1) + info.get(i).get(j));
                    continue;
                }
                // 중간에 있는 case
                info.get(i).set(j, Math.max(info.get(i - 1).get(j - 1), info.get(i - 1).get(j)) + info.get(i).get(j));
            }
        }

        Integer a = info.get(n - 1).stream().max(Comparator.comparing(x -> x)).orElse(1);
        System.out.println(a);
    }
}

 

 

import java.util.Arrays;
import java.util.Scanner;

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