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

문제

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

1932번: 정수 삼각형

 

 

풀이

전에 비슷한 문제를 풀어봤던 것 같다!

암튼 그래서 쉽게 풀었음 ㅎㅎ

 

동적계획법 문제가 나오면 평소처럼 생각하지 말고 거꾸로 생각하거나 밑에서부터 계산해보거나 처음 결과를 가지고 다음 계산에 이용한다거나 등의 접근 방식이 필요하다

 

이 문제에서는 위에서 아래 층으로 내려온다고 나와있지만 밑에서 부터 올라가는 식으로 계산을 하면 어떨까... 하는 생각으로 풀었다!

 

자세한건 주석으로!

 

 

코드

// 1932번 정수 삼각형
// https://www.acmicpc.net/problem/1932

package BAEKJOON;

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

public class Num1932_정수삼각형 {
    static int n;
    static int[][] arr; // 처음 입력받은 정수 삼각형
    static int[][] answerArr; // 정답을 구하기 위한 이차원 배열

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

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

        arr = new int[n][n];
        answerArr = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                if (i >= j) { // 삼각형 모양으로 입력받기
                    arr[i][j] = Integer.parseInt(st.nextToken());
                } else {
                    break;
                }
            }
        }

        // 정수 삼각형의 맨 밑줄은 그대로 정답 배열에 복사
        for (int i = 0; i < n; i++) {
            answerArr[n - 1][i] = arr[n - 1][i];
        }

        // 맨 밑에서 부터 더하면서 올라오기
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (n - i - 1 >= j) {
                    answerArr[n - i - 2][j] = Math.max(answerArr[n - i - 1][j] + arr[n - i - 2][j], answerArr[n - i - 1][j + 1] + arr[n - i - 2][j]);
                }
            }
        }

        // 정답 출력
        System.out.println(answerArr[0][0]);
    }
}