백준 1932번 정수삼각형 JAVA

DP문제이다. 이전 층에 있던 삼각형의 합을 메모라이제이션 해서 원하는 층에서 그 저장해 놨던 값을 재사용 함으로서 연산의 회수를 줄인다. Bottom up 방식으로 풀었다.

만약 DP를 사용하지 않고 완전탐색으로 푼다면,

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

 

위와 같은 정수 삼각형이 있다고 가정을 하면,
각 층마다 조합으로 한가지를 선택하는 것이기 때문에
1C1 * 2C1 * 3C1 * 4C1 * 5C1로 결론적으로
5!의 시간복잡도가 나타나게 된다.

층수를 입력범위중 최대인 500이면 500!의 시간복잡도가 나타나기 때문에 불가능하다.
따라서, 또 다른 정수 합의 저장을 위한 리스트를 만들고

         7
      10   15
    18   16   15
  20   25   20   19
24   30   27   26   24

 

와 같이 층을 거듭할수록 이전 층에 계산한 값을 재사용(메모라이제이션)을 함으로서 복잡도를 크게 줄인다.

이와같은 방식을 통해서 구하게 된다면 시간복잡도는 O(n^2)이 되게 된다.

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

public class Main {
    static List<List> DP;
    static List<List> triangle;
    public static void go(int layser,int N){
        if(layser==N){
            return;
        }
        for(int i=0;i<triangle.get(layser-1).size();i++){
            for(int j=i;j<i+2;j++){
                DP.get(layser).set(j,Math.max((Integer) triangle.get(layser).get(j)+(Integer)DP.get(layser-1).get(i),(Integer)DP.get(layser).get(j)));
            }
        }
        go(layser+1,N);
    }

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

        int N = Integer.parseInt(br.readLine());
        triangle = new ArrayList<>();
        DP = new ArrayList<>();
        int temp = 0;
        for(int i=0;i<N;i++){
            st=new StringTokenizer(br.readLine());
            triangle.add(new ArrayList<Integer>());
            DP.add(new ArrayList<Integer>());
            while (st.hasMoreTokens()){
                triangle.get(i).add(Integer.parseInt(st.nextToken()));
                DP.get(i).add(-1);
            }
        }
        DP.get(0).set(0,triangle.get(0).get(0));
        go(1,N);
        int answer = -1;
        for(int i=0;i<N;i++){
            answer=Math.max(answer, (Integer) DP.get(N-1).get(i));
        }
        System.out.print(answer);
    }
}