🥈 [Baekjoon / Java] 1932. 정수 삼각형

문제 설명

💡 Info

• 난이도 : 실버 1
• 시간 제한 : 2초
• 메모리 제한 : 128MB
• 백준 링크: https://www.acmicpc.net/problem/1932
  풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Sliver/1932. 정수 삼각형

내용

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

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

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

📥입력 조건

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

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

📤출력 조건

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

  30

문제 이해

• 다이나믹 프로그래밍을 이용해 나눠서 합 출력하기!

알고리즘 및 최종 풀이

실제 풀이 시간 : 15분

• 입력
  • N 입력받기
  • 2차원 배열 TD 입력받기
  • 2차원 배열 arr 입력받기
• 계산
  • D 테이블 초기화
  • 다이나믹 프로그래밍 실행: 왼쪽 위와 그냥 위를 나눠서 구현
• 출력
  • 결과 result 출력하기

import java.util.*;

public class Main {

  static int N;
  static int[][] TD;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    N = sc.nextInt();

    TD = new int[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < i + 1; j++) {
        TD[i][j] = sc.nextInt();
      }
    }

    for (int i = 1; i < N; i++) {
      for (int j = 0; j <= i; j++) {
        int LUp, Up;
        if (j == 0) {
          LUp = 0;
        } else {
          LUp = TD[i - 1][j - 1];
        }

        if (j == i) {
          Up = 0;
        } else {
          Up = TD[i - 1][j];
        }
        TD[i][j] = TD[i][j] + Math.max(LUp, Up);
      }
    }
    int result = 0;
    for (int i = 0; i < N; i++) {
      result = Math.max(result, TD[N - 1][i]);
    }
    System.out.println(result);
  }
}