Calm Dawn Studio

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

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));

		int n = Integer.parseInt(br.readLine());

		int[][] triangle = new int[n][0];
		int[][] solutionDp = new int[n][0];
		int maxNum = 0;

		// 초기 정수 삼각형
		for (int i = 0; i < triangle.length; i++) {
			triangle[i] = new int[i + 1];
			solutionDp[i] = new int[i + 1];
		}

		// 정수 삼각형 내부의 값을 채움
		for (int i = 0; i < triangle.length; i++) {
			StringTokenizer inputSt = new StringTokenizer(br.readLine()); // 삼각형 한줄의 값

			for (int j = 0; j < triangle[i].length; j++) {
				triangle[i][j] = Integer.parseInt(inputSt.nextToken());
			}
		}

		solutionDp[0][0] = triangle[0][0];

		// 정수 삼각형 내부 값 탐색 -> 마지막 줄 이전까지만 실행함
		for (int i = 0; i < triangle.length - 1; i++) {
			for (int j = 0; j < triangle[i].length; j++) {
				solutionDp[i + 1][j] = Math.max(solutionDp[i + 1][j], solutionDp[i][j] + triangle[i + 1][j]);
				solutionDp[i + 1][j + 1] = Math.max(solutionDp[i + 1][j + 1],
						solutionDp[i][j] + triangle[i + 1][j + 1]);
			}
		}

		for (int num : solutionDp[n - 1]) { // 마지막 줄 최대 경로값 탐색
			maxNum = Math.max(maxNum, num);
		}

		bw.write(String.valueOf(maxNum));
		bw.flush();
		bw.close();
	}

}

처음 문제에 접근한 방식

1. 초기 입력받은 삼각형과 동일한 구조의 배열을 선언함

2. 삼각형의 맨 위 -> 아래로 내려오면서 각 위치의 왼쪽아래 오른쪽아래를 탐색하고 최소값을 비교함 

3. solutionDP[] 배열을 clone() 메서드를 통해 복사해서 결과값 출력하니 오답 발생.

4. clone()메서드의 경우 이차원 배열, 객체를 복사하는경우 깊은복사가 아닌 얕은 복사가 이루어짐

정답을 맞춘 풀이방법

1. solutionDP[] 배열을 초기 입력받을 배열과 동일한 방식으로 선언한 뒤 문제 해결함