백준 1932번 정수 삼각형(JAVA,DP)

<풀이방식>

삼각형 모양으로 배열에 값을 저장하는걸 할줄몰라서 처음에 애를 좀먹었음.

다음과 같이 간단하게 작성가능한데, 저걸 몰랐어서 카운트세면서 브레이크 거는 방식으로 구현했다.

그리고 배열에 첫번째 열은 0으로 채워주어 인덱스 오류를 방지했고
arr[i][j] += Math.max(arr[i-1][j-1], arr[i-1][j]); 라는 간단한 점화식으로 해결했다.
이렇게 되면 마지막 열에 최대값들이 누적되어있는데 이중에 최대값을 뽑아 출력했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int [][] arr = new int [n][n+1];

		for(int i = 0 ; i < n ; i ++) {
			int cnt = 0;
			for(int j = 1 ; j < n+1 ; j++) {
				arr[i][j] = sc.nextInt();
				cnt++;
				if(i+1 == cnt)
					break;
			}
		}

		
		
		//초기값 설정
		arr[1][1] += arr[0][1];
		arr[1][2] += arr[0][1];
		for(int i = 2 ; i < n ; i ++) {
			for(int j = 1; j < n+1; j++) {
				//점화식  : 내 위에 2개중에 큰거를 선택해서 나한테 더해감
				arr[i][j] += Math.max(arr[i-1][j-1], arr[i-1][j]);
			}
		}
		
		int max = 0;
		for(int i =0 ; i < n+1 ; i++) {
			if(max < arr[n-1][i]) {
				max = arr[n-1][i];
			}
		}
		/*
		for(int i = 0 ; i < n ; i++) {
			System.out.println();
			for(int j = 0 ; j < n+1;j++) {
				System.out.printf("%d ", arr[i][j]);
			}
		}
		*/
		
		System.out.printf("%d", max);
	}


}