정수 삼각형 1932

LJM·2023년 3월 21일
0

백준풀기

목록 보기
150/259

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

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 size = (int)Math.pow(2, N) -1;

        int[][] tri = new int[N][];

        String[] input;
        for (int i = 0; i < N; i++)
        {
            tri[i] = new int[i+1];
            input = br.readLine().split(" ");
            for (int j = 0; j < i+1; j++)
            {
                tri[i][j] = Integer.parseInt(input[j]);
            }
        }

        int[][] dp = new int[N][];
        for (int i = 0; i < N; i++)
        {
            dp[i] = new int[tri[i].length];
        }

        dp[0][0] = tri[0][0];

        for (int i = 1; i < N; i++)
        {
            for (int j = 0; j < dp[i].length; j++)
            {
                if(j == 0)
                    dp[i][j] = tri[i][j] + dp[i-1][j];
                else if(j == dp[i].length-1)
                    dp[i][j] = tri[i][j] + dp[i-1][j-1];
                else
                    dp[i][j] = tri[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
            }
        }

        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            ans = Math.max(ans, dp[N-1][i]);
        }

        System.out.println(ans);
    }
}
profile
게임개발자 백엔드개발자

0개의 댓글