/ BOJ

BOJ_1932_정수삼각형_JAVA

문제 : 정수 삼각형

링크 : BOJ_1932_정수삼각형

접근 방식

DP 카테고리에 있는 문제이기 때문에 DP의 개념을 어떻게 적용해서 사용할 지 고민이 되었다.

삼각형을 계층적으로 나누어보면, 상위에 있는 수는 하위의 두 개의 수에 영향을 끼칠 수 있다. 따라서 가장 최상위부터 시작하여 값을 아래로 누적시켜 내려가는데, 누적을 시킬 때 이전계층의 수의 최댓값을 구해서 누적시키면 최종적으로 가장 하위계층으로 도착했을 때 가능한 모든 최댓값을 누적한 값이 저장되어있을 것이다.

사실 이 문제가 어떤 부분에서 DP를 적용시켰는지 이해하지는 못했다. 값을 누적시켜가는 것이 메모이제이션의 개념이라고 생각한다면 생각할 수 있을 것 같다.

소스 코드


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

public class BOJ_1932_정수삼각형 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		int arr[][] = new int[N + 1][N + 1];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j <= i; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int dp[][] = new int[N + 1][N + 1];

		dp[0][0] = arr[0][0];

		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j <= i; j++) {
				// 이전 계층의 최댓값 누적
				dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
				dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j]);
			}
			// 해당 위치의 원래 수 더하기
			for (int j = 0; j <= i+1; j++) {
				dp[i + 1][j] += arr[i+1][j];
			}
		}
		int answer = 0;
		for (int i = 0; i < N; i++) {
			answer = Math.max(answer, dp[N-1][i]);
		}
		System.out.println(answer);

	}

}