백준 : 1932 (정수 삼각형) (DP)

이번문제는 쉬운듯 하면서도 어렵게 느껴졌던 문제이다.

 

그이유는 아무래도 익숙하지 않아서 그런것 같다.

 

처음에 2차원 배열말고, 1차원 배열로 적용하자니 왼쪽 위, 오른쪽 위의 인덱스를 찾아서 더해주는 부분을 구현하는데 애를 먹었다.

 

검색을 해보니 2차원 배열을 이용하는 내용이 있어, 참고 할 수 있었다.

import java.util.*;

class Main {
	static int n, result = 0;
	static int[][] dp;

	public static void dp() {
		for (int i = 1; i < n; i++) { // dp[0][0] 제외
			for (int j = 0; j <= i; j++) { // 삼각형이므로 i == j 가 끝이다.
				if(j == 0) { //가장 왼쪽이면 오른쪽위에 선택
					dp[i][j] += dp[i-1][j]; 
				}
				else if(j == i) { //가장 오른쪽이면 왼쪽위에 선택
					dp[i][j] += dp[i-1][j-1]; 
				}
				else { //양쪽위에가 다 있다면 더 큰값으로 대체
					dp[i][j] += Math.max(dp[i-1][j], dp[i-1][j-1]); 
				}
			}
		}

	}

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

		n = sc.nextInt();
		sc.nextLine();

		dp = new int[n][n];

		for (int i = 0; i < n; i++) {
			String st = sc.nextLine();
			String[] stArr = st.split(" ");

			for (int j = 0; j < stArr.length; j++) {
				dp[i][j] = Integer.parseInt(stArr[j]);
			}
		}

		dp();
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				result = Math.max(dp[i][j], result);
			}
		}
		
		System.out.println(result);

	}
}