[백준] 1932. 정수 삼각형

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

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

 

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

 

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

 

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

---

입력

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

출력

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

---

예제 입력 1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1

30

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] arr;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[sumN(N)];
        int idx = 1;
        int max = Integer.MIN_VALUE;
        arr[0] = 0;

        for(int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 1; j <= i; j++) {
                int num = Integer.parseInt(st.nextToken());
                if(j == 1) {
                    arr[idx] = arr[idx - (i - 1)] + num;
                } else if (j == i) {
                    arr[idx] = arr[idx - i] + num;
                } else {
                    // 사이값 비교
                    if(arr[idx - i] > arr[idx - i + 1]) {
                        arr[idx] = arr[idx - i] + num;
                    } else {
                        arr[idx] = arr[idx - i + 1] + num;
                    }
                }
                
                if(arr[idx] >= max) {
                    max = arr[idx];
                }
                idx++;
            }

        }
        
        System.out.println(max);
    }

    public static int sumN(int n) {
        int sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += i;
        }

        return sum + 1;
    }
}

자신의 현재 위치로부터 다음 Index를 접근했을 때 어느 값이 더 큰지 비교하면서 아래로 내려간다. 다음 인덱스로 갈 때 이전 값을 arr배열에 계속 저장해나간다.

 

                0
                1
              2   3
            4   5   6
          7   8   9  10
        11  12  13  14  15
 해당 삼각형의 Index의 규칙을 찾아서 접근한다.