1932 : 정수 삼각형

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

---

문제

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

 

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

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

출력

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

---

접근

• 문제에서, '이제까지 선택된 수의 합이 최대~'라고 한 것을 보고, 매 순간 최댓값을 선택하는 것임을 알 수있다. 즉, 현재 최댓값을 선택하면, 결과도 최댓값이 될 것을 예상한다. 
• 삼각형에서, n번째 층의 맨 왼쪽 숫자부터 1, 2, ..., k, ... m번째 수라고 하자.
• n번째 층의 1번째 수는, (n-1)번째 층의 1번째 수에 자신의 값을 더한 것이 최댓값이다. 
• n번째 층의 m번째 수는, (n-1)번째 층의 m번째 수에 자신의 값을 더한 것이 최댓값이다. 
• n번째 층의 k번째 수는, (n-1)번째 층의 (k-1)번째 수와, k번째 수 중 큰 값에 자신의 값을 더한 것이 최댓값이다. 
• 위 세가지로 나누어 반복문을 돌리면, 마지막 층에 우리가 원하는 값이 있을 것이다. 

---

코드

package beak;
 
import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n + 1][n + 1];
        int max = 0;
 
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= i; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (j == 1) {
                    map[i][j] += map[i - 1][j];
                } else if (j == i) {
                    map[i][j] += map[i - 1][j - 1];
                } else {
                    map[i][j] += Math.max(map[i - 1][j - 1], map[i - 1][j]);
                }
 
                if (max < map[i][j])
                    max = map[i][j];
            }
        }
 
        bw.write(max + "\n");
 
        bw.flush();
        br.close();
 
    }
}