[JAVA] 백준 1932 - 정수 삼각형

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

1932번: 정수 삼각형

 

🤔 문제 접근

전체 숫자들의 최대값 정보를 담는 2차원 배열 tree와 원래 숫자의 정보를 담는 2차원 배열 ori를 선언했다.

tree.clone으로 ori도 생성을 간단하게 하면 되지 않을까 생각했지만

2차원 배열에 clone메서드를 사용하면 객체들을 담고 있는 주소의 주솟값데이터를

새로 생성해 복사하기 때문에, (2차원 배열에 clone을 사용하면 얉은 복사를 수행, 1차원 배열은 깊은 복사)

tree [i][j]의 값이 바뀌면 ori [i][j] 의 값도 바뀌게 되므로 2중 for문을 통해 새로이 ori 2차원 배열을 생성했다.

 

이 문제에서는 parent 의 배열 위치 i, j에서 i + 1 이며 j 값이 같은 위치

그리고 i + 1 이며 j + 1인 위치의 값만 신경써 최대값을 갱신하면 되었다. 이것은

 

tree[i+1][j] = Math.max(parent + ori[i+1][j], tree[i+1][j]);

tree[i+1][j+1] = Math.max(parent + ori[i+1][j+1], tree[i+1][j+1]);

로 나타낼 수 있겠다.

이 과정은 n - 1 까지 수행된다.

 

최대값 갱신 작업이 끝나면 마지막 i = n 의 위치에 있는 모든 배열 값들 중

최대 값을 찾아서 출력하면 된다.

 

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[][] tree = new int[n+1][n+1];
		int[][] ori = new int[n+1][n+1];
		
		for(int i = 1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 1; j<=i; j++) {
				tree[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=i; j++) {
				ori[i][j] = tree[i][j]; 
			}
		}
		
		// ori 배열을 tree.clone으로 생성하면 얉은 복사를 하므로 불가
		// i = 층, j는 i층의 j번째를 뜻함
		// 부모숫자는 자기 아래층이며 자기와 같은 index, index+1인 수에 더해짐
		
		for(int i = 1; i<=n-1; i++) {
			for(int j = 1; j<=i; j++) {
				int parent = tree[i][j];
				int o1 = ori[i+1][j];
				int o2 = ori[i+1][j+1];
				int c1 = tree[i+1][j];
				int c2 = tree[i+1][j+1];
				tree[i+1][j] = Math.max(o1 + parent, c1);
				tree[i+1][j+1] = Math.max(o2 + parent, c2);
			}
		}
		
		int result = 0;
		for(int i = 1; i<=n; i++) {
			result = Math.max(result, tree[n][i]);
		}
		
		System.out.println(result);
	}	

}