[BOJ 1932] 정수 삼각형 (Java)

문제

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

1932번: 정수 삼각형

정수 삼각형

풀이

7 7
3 10	8 15
8 18	1 16	0 15
2 20	7 25	4 20	4 19
4 24	5 30	2 27	6 26	5 24

2차 배열에 최대값을 저장하면서 더해나간다. 

첫번째 값 dp[i][j] = num + dp[i-1][j];

마지막 값 dp[i][j] = num + dp[i-1][j-1];

나머지 값 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]);

 

마지막 행의 최대값을 구한다. 

N이 1일 경우 for문 내에서 최대값이 저장되지 않으므로, 따로 예외처리를 해주었다. 

소스코드

package dp;

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

public class BOJ1932 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = 0;
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N+1][N+1];
        StringTokenizer st = null;
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= i; j++){
                dp[i][j] = Integer.parseInt(st.nextToken());
                if(i == 1 && j == 1) continue;
                if(j == 1){
                    dp[i][j] += dp[i-1][j];
                } else if(j == i){
                    dp[i][j] += dp[i-1][j-1];
                } else {
                    dp[i][j] += Math.max(dp[i-1][j-1], dp[i-1][j]);
                }
                if(i == N){
                    answer = Math.max(dp[i][j], answer);
                }
            }
        }
        if(N == 1){
            System.out.println(dp[1][1]);
        } else {
            System.out.println(answer);
        }
    }
}