[백준] 1932번 숫자 삼각형

- 문제 : https://www.acmicpc.net/problem/1932

 피라미드 모양으로 구성된 숫자들을 특정 기준에 맞게 더할 경우에 나올 수 있는 최대값을 구하는 문제입니다. 숫자는 아래 방향으로 인접한 두 수를 더할 수 있습니다. 문제에대한 정확한 설명을 링크를 참조해주세요.

- 풀이

      7

    3 8

   8 1 0

 2 7 4 4

4 5 2 6 5

 위 모양으로 구성된 피라미드의 경우에 7은 3과 8을 더할 수 있습니다. 7이 3과 8을 더해서 나온 값들인 10과 15의 경우에 10은 8과 1을 더할 수 있고 15는 1과 0을 더할 수 있습니다. 이렇게 더해가는 과정을 반복하면 마지막에 이르게 되는데 그때 최대값을 찾아주면 됩니다.

 처음에는 무조건 위에서 아래로 더해주는 경우를 생각했고 2개의 부모와 더해지는 값을 중심으로 코드를 작성하려 했습니다. 2개의 부모란 마지막 줄의 5, 2, 6을 의미합니다. 이 경우에는 (2,7), (7,4), (4,4) 와 같이 두개의 부모들과 더해진 값을 비교해서 그 중에 큰 수를 찾아야 합니다. 위에서 아래로 내려오는 경우에 for문을 이용하면 조금 복잡하다는 사실을 알았고 다른 방법을 생각해봤습니다.

 그래서 아래에서 위로 올라가는 방법으로 해결했습니다. for문을 구성할때도 덜 복잡하고 쉽게 해결할 수 있습니다. 먼저 left, right값을 설정 했습니다. 5번째 줄에서 첫번째 left는 4, right는 5 입니다. 이 경우에 left, right가 공통으로 갖고있는 부모의 값인 2와 left, right를 더해줬고 큰 값을 부모의 자리에 할당했습니다. 부모의 자리에 할당한 이유는 이제 부모의 값은 필요없고 더해진 값 중에 최대값으로 대체해서 다음 줄의 비교에 사용했습니다. 그리고 마지막으로 제일 상단인 triangle[0][0]에는 모든 경우를 비교했을때 최대값이 저장됩니다.

- 코드

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

public class NumbericTriangle {
	BufferedReader br;
	int n;
	int[][] triangle, result;

	void setValues() {
		String[] temps;
		br = new BufferedReader(new InputStreamReader(System.in));
		try {
			n = Integer.parseInt(br.readLine());
			triangle = new int[n][n];
			result = new int[n][n];

			for (int i = 0; i < n; i++) {
				temps = br.readLine().split(" ");
				for (int j = 0; j < i + 1; j++) {
					triangle[i][j] = Integer.parseInt(temps[j]);
				}
			}
		} catch (NumberFormatException | IOException e) {
			e.printStackTrace();
		}
	}

	public void solve() {
		int left, right, parent;
		setValues();

		for (int i = n - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				left = triangle[i][j];
				right = triangle[i][j + 1];
				triangle[i - 1][j] = Math.max(left + parent, right + parent);
			}
		}
		System.out.println(triangle[0][0]);
	}

	public static void main(String[] args) {
		NumbericTriangle m = new NumbericTriangle();
		m.solve();
	}

}