백준 1932 자바 DP 풀이

연두색 부분은 j == 0 일때

하늘색 부분은 i == j 일때

보라색 부분은 둘다 해당되지 않는 경우이다.

 

현재 i 행의 j번째 위치까지의 최대 합은 i행의 j번째로 입력 받은 값

triangle[i][j]와 이전 i - 1행의 j - 1번째 triangle[i - 1][j - 1] 혹은 j번째까지의 합 triangle[i - 1][j] 중 최대값을 더한 값이다.

단, 0번째 위치의 값은 j - 1번째가 존재하지 않고 삼각형의 끝 위치에 있는 값은

j번째 값이 존재하지 않으므로 예외 처리를 해준다.

 

코드로 나타내면 다음과 같다.

import java.io.*;
import java.util.StringTokenizer;

public class t1932 {
  static int[][] triangle;
  static BufferedReader br;
  static BufferedWriter bw;
  static StringTokenizer st;
  public static void main(String[] args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));
    bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());

    triangle = new int[N + 1][N + 1];

    triangle[0][0] = Integer.parseInt(br.readLine());

    bw.write(dp(N)+"");

    br.close();
    bw.flush();
    bw.close();
  }
  private static int dp(int n) throws IOException {
    int max = 0;
    for(int i = 1; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      for(int j = 0; j <= i; j++) {
        triangle[i][j] = Integer.parseInt(st.nextToken());

        if(j == 0)
          triangle[i][j] += triangle[i - 1][j];
        else if(j == i)
          triangle[i][j] += triangle[i - 1][j - 1];
        else
          triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);

        max = Math.max(max, triangle[i][j]);

      }
    }
    return max;
  }
}