[JAVA] 백준 (실버1) 1932번 정수 삼각형

링크

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

---

문제 설명

정답률 59.723%

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

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

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

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

---

입력 예제

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

---

출력 예제

30

---

풀이

최 상단부터 한 칸씩 내려가면서 최댓값을 갱신해나간다. 모서리의 경우 좌측은 0번 인덱스, 우측은 자기 인덱스에서 - 1 해준 값을 더해가고 중간에 있는 값들은 자기 인덱스 - 1, 자기 인덱스의 값 중에 최댓값을 받아 갱신해나간다.

for (int i = 1; i < N; i++) {
    for (int j = 0; j < length[i]; j++) {
        //좌측 모서리
        if (j == 0) {
            tri[i][j] += tri[i - 1][j];
        }
        //우측 모서리
        else if (j == length[i] - 1) {
            tri[i][j] += tri[i - 1][j - 1];
        }
        //모서리가 아닐 경우
        else {
            tri[i][j] += Math.max(tri[i - 1][j - 1], tri[i - 1][j]);
        }
    }
}

반복문을 모두 수행하면 마지막 열에는 결괏값들이 저장되는데 이 중에서 다시 최댓값이 정답이 된다.

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int[][] tri = new int[N][N];
        int[] length = new int[N];

        //각 레벨의 가로 길이
        for (int i = 0; i < N; i++) {
            length[i] = i + 1;
        }

        //입력값 초기화
        for (int i = 0; i < N; i++) {
            int index = 0;
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                tri[i][index++] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i < N; i++) {

            for (int j = 0; j < length[i]; j++) {
                //좌측 모서리
                if (j == 0) {
                    tri[i][j] += tri[i - 1][j];
                }
                //우측 모서리
                else if (j == length[i] - 1) {
                    tri[i][j] += tri[i - 1][j - 1];
                }
                //모서리가 아닐 경우
                else {
                    tri[i][j] += Math.max(tri[i - 1][j - 1], tri[i - 1][j]);
                }
            }
        }

        //마지막 열의 최댓값 출력
        Arrays.stream(tri[N - 1])
                .max()
                .ifPresent(System.out::println);
    }
}