[백준 1932] 정수 삼각형

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

DP 문제입니다

일단 삼각형을 입력 받을시 (배열로)

해당 행의 최대값을 바로 구해넣어 주시면 됩니다.

3가지 경우를 체크해주시면 되는데,

2 가지 경우는 왼쪽 대각선으로만 움직엿을 경우와 오른쪽 대각선으로만 움직였을 경우 처리를 해주시고

나머지 한 경우는 (현재 입력값 + 현재의 상단 좌/우값 중) 의 최대값을 넣어주시면 됩니다.

결과적으로 입력받음과 동시에

         7

      10  15

    18  16  15

  20  25  20  19

24  30  27  26  24

이런 형태가 되겠죠? 

이런 방법으로 푸시면 되겠습니다.

 

public class Q1932 {
    static int[][] arr;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        
        arr = new int[num+1][num+1];
        int sum = 0;
        for(int i=1; i<arr.length; i++) {
        	for(int j=1; j<=i; j++) {
        		arr[i][j] = in.nextInt();
        		
        		if(j==1) {
        			arr[i][j] += arr[i-1][j];
        		}else if(j==i) {
        			arr[i][j] += arr[i-1][j-1];
        		}else {
        			arr[i][j] += Math.max(arr[i-1][j-1], arr[i-1][j]);
        		}
        		if(arr[i][j]>sum) {
        			sum = arr[i][j];
        		}
        	}
        }
        System.out.println(sum);
    }
}

배열의 크기를 입력받은 값 + 1 을 해주는 이유는

만약에 입력받은 값의 사이즈로 배열을 만들었을경우

반복문안에서 예외부분에 대한 처리를 해줘야되는 코드가 많아지기 때문입니다