[BOJ] 1932. 정수 삼각형

문제

풀이

개인적으로 DP 로직 구현보다 배열 관리에서 더 헤맸던 문제...
처음에 설계를 좀 더 구체적으로 했어야 했는데 그러지 않고 풀어서 그랬던 것 같다ㅜ
for문을 이용해서 bottom-up 방식으로 구현했다!

해당 그림처럼 i행 마다 i+2의 배열 크기를 할당해주었다.
for(int i=0;i<N+1;i++) arr[i] = new int[i+2];

DP 로직은 현재 위치(i,j)를 기준으로 현재 위치의 DP[i-1,j-1],DP[i-1][j] 중에서 더 큰값을 뽑고 현재 위치 값 arr[i][j]을 더하는 형태로 구현했다.
그리고 마지막에 DP[N] 중 최대값을 출력하면 된다.

JAVA코드

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

public class 백준1932_정수삼각형 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N + 1][];

		for (int i = 1; i < N + 1; i++) {
			arr[i] = new int[i + 2];

			st = new StringTokenizer(br.readLine());

			for (int j = 1; j < i + 1; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

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

		DP[1][1] = arr[1][1];

		for (int i = 2; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				DP[i][j] = Math.max(DP[i - 1][j - 1], DP[i - 1][j]);
				DP[i][j] += arr[i][j];
			}

		}

		int max = Integer.MIN_VALUE;
		for (int i = 1; i <= N; i++) {
			max = max < DP[N][i] ? DP[N][i] : max;
		}

		System.out.println(max);

	}

}