백준 1932(JAVA)

문제

풀이

맨 위에서부터 한 레벨씩 내려가면서, 왼쪽 아래, 왼쪽 오른쪽의 합을 더하며 dp 테이블에 값을 저장하면 된다.
높이는 최대 500이고, 내려가면서 현재 높이의 개수 * 2만큼 탐색하므로(2 + 4 + 6 + 8 + ... + 1000) 시간초과 날 걱정은 안해도된다.
물론 문제에서 풀라는 것과같이 이미 값이 있으면 최대값으로 dp 테이블을 갱신해 나가며 풀면된다.

반복문을 이용한 bottom up으로 dp테이블에 값을 적어가며 메모이제이션을 구현했고 해당 메모된 값을 계속 업데이트하며 문제를 풀었다.

나는 ArrayList를 이용했다.

코드

package baekjoon.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main1932 {
    static int N;
    static List<List<Integer>> triangle = new ArrayList<>();
    static List<List<Integer>> dp = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++){
            triangle.add(new ArrayList<>());
            dp.add(new ArrayList<>());
        }
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j <= i; j++){
                triangle.get(i).add(Integer.parseInt(st.nextToken()));
                dp.get(i).add(-1);
            }
        }

        dp.get(0).set(0, triangle.get(0).get(0));

        for(int i = 0; i < N - 1; i++){
            for(int j = 0; j < dp.get(i).size(); j++){
                if(dp.get(i + 1).get(j) == -1){
                    dp.get(i + 1).set(j, dp.get(i).get(j) + triangle.get(i + 1).get(j));
                }else{
                    dp.get(i + 1).set(j,
                            Math.max(dp.get(i + 1).get(j), dp.get(i).get(j) + triangle.get(i + 1).get(j))
                    );
                }
                if(dp.get(i + 1).get(j + 1) == -1){
                    dp.get(i + 1).set(j + 1, dp.get(i).get(j) + triangle.get(i + 1).get(j + 1));
                }else{
                    dp.get(i + 1).set(j + 1,
                                Math.max(dp.get(i + 1).get(j + 1), dp.get(i).get(j) + triangle.get(i + 1).get(j + 1))
                            );
                }
            }
        }


        System.out.println(Collections.max(dp.get(N - 1)));

    }
}