백준 1932 정수 삼각형(JAVA)

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

1932번: 정수 삼각형

 

 

 

풀이)

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

public class Main_BJ_1932_정수삼각형 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] tree = new int[n][n];
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<=i; j++){
                tree[i][j] = Integer.parseInt(st.nextToken());
                if(i==n-1){
                   dp[i][j] = tree[i][j];
                }
            }
        }//for

        for(int i=n-2; i>=0; i--){
            for(int j=0; j<=i; j++){
                dp[i][j] = Math.max(dp[i+1][j] + tree[i][j], dp[i+1][j+1]+tree[i][j]);
            }
        }
        System.out.println(dp[0][0]);
    }//main
}

이차원 배열인 tree라는 배열과 dp 배열을 선언한다.

 

밑에서부터 최대값을 선택하여 더해서 올라가는 방식을 사용했다!

이때, 맨 마지막 줄은 tree와 같은 값을 넣어두고, 더하면서 올라가면 된다.

 

처음에는 이진 트리처럼 구해서 사용하려 했는데, 아니라는걸 깨닫고 바로 바꿨다..

이후 dp배열의 맨 꼭대기를 출력하면 끝!!

 

30

23 21

20 13 10

7 12 10 10

4 5 2 6 5

=> 이런 식으로 dp배열이 나오게 된다