[Java] BOJ 1932번 정수 삼각형

1932번: 정수 삼각형

---

풀이

문제의 조건에 있는 "아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다."를 DP에 적용하여 해결했습니다.

이때, i - 1을 할 경우 i가 0보다 작아질 수 있으니 이를 방지하기위해 배열의 크기를 [N + 1][N + 1]로 만들어 [1][1] 부터 수를 채우게했습니다.

---

코드

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

public class Main {
	public static int N;
	public static int[][] triangle;
	public static int[][] memo;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		
		triangle = new int[N + 1][N + 1];
		memo = new int[N + 1][N + 1];
		
		for (int i = 1; i <= N; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			
			for (int j = 1; j <= i; ++j) {
				triangle[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= i; ++j) {
				memo[i][j] = Math.max(memo[i - 1][j], memo[i - 1][j - 1]) + triangle[i][j];	
			}
		}
		
		int answer = 0;
		for (int i = 1; i <= N; ++i) {
			answer = (answer < memo[N][i]) ? memo[N][i] : answer;
		}
		
		System.out.println(answer);
	}
}

---

pyo7410/Algorithm