[백준] 1932 정수 삼각형 - Dynamic Programming / Java

• 문제 링크

1932번: 정수 삼각형

 

• 풀이 과정

정수 삼각형을 일종의 트리 구조로써, 경로의 합의 최댓값을 구하기 위해 위층이 아닌 아래층부터 탐색하여 풀이한다.

 

맨 하단의 두 자식 노드 중 큰 값을 부모 노드에 더해 부모 노드를 갱신하는 방식으로 루트 노드까지 탐색해나간다.

문제에 제시된 입력을 위의 방법으로 접근하여 최종적으로 변화된 정수 삼각형의 값을 나타내면 아래와 같다.

         30
       23   21
     20  13   10
   7   12   10   10
 4    5   2    6    5

이를 i는 감소하고 j 는 증가하는 2중 for 문 안에 arr[i - 1][j] += Math.max(arr[i][j], arr[i][j + 1]) 로 구현하고,

탐색을 끝낸 후 루트 노드인 arr[0][0] 의 값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j <= i; j++)
				arr[i][j] = Integer.parseInt(st.nextToken());
		}

		for (int i = n - 1; i > 0; i--) {
			for (int j = 0; j < i; j++)
				arr[i - 1][j] += Math.max(arr[i][j], arr[i][j + 1]);
		}

		bw.write(arr[0][0] + "\n");
		bw.flush();
	}

}