[백준] 1932. 정수 삼각형

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

 

dp 문제 중 비교적 쉽게 풀어냈다. 

 

 

아래 숫자에서 위의 숫자들 중 가장 큰 값을 가진 숫자를 더하는 식으로 dp 점화식을 세웠다. 

 

• 맨 왼쪽 또는 오른쪽에 위치한 숫자들은 대각선에 있는 숫자 하나를 선택할 수 있다. 
• 그 외에는 두 숫자 중 큰 값을 선택해 더한다. 

따라서 
j == 0 일 때는 dp[i-1][j] + arr[i][j]
j == cnt -1 일 때는 dp[i-1][j-1] + arr[i][j] 
그 외에는 Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j] 로 점화식을 세웠다. 

 

풀이 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][N];
        int[][] dp = new int[N][N];
        int max = 0;
        int cnt = 1;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < cnt; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = arr[i][j];
                if (i > 0 && j == 0) {
                    dp[i][j] = dp[i - 1][j] + arr[i][j];
                } else if (i > 0 && j == cnt - 1) {
                    dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
                } else if (i > 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j];
                }
                max = Math.max(max, dp[i][j]);
            }
            cnt++;
        }
        System.out.println(max);
    }
}

 

입력을 받으면서 dp 배열을 채웠기 때문에 cnt를 따로 두어 풀이하였다.