[백준] 1932번 : 정수 삼각형 (JAVA)

1. 문제 분석

DP문제이다. 크기를 1씩 늘려가면서 1,2,3, ... , N번째 삼각형까지 메모이제이션을 활용해서 최댓값을 찾으면 된다.

 

시간복잡도 : O(N^2) 

알고리즘 : DP

2. 문제 풀이

삼각형 크기를 1씩 늘려가면서 최댓값을 구한다.

• n번째 열에서 각 항의 최댓값
• dp[n][i] = Math.max(dp[n-1][i] + value[n][i], dp[n-1][i-1] + value[n][i])

 

3. 코드 구현

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

public class BOJ_1932 {

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

        int N = Integer.parseInt(st.nextToken());
        int[][] num = new int[N+1][N+1];
        int[][] dp = new int[N+1][N+1];

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= i; j++){
                num[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

            }
        }

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

        System.out.println(answer);

    }
}