백준 1932번 JAVA

딱봐도 풀이방법이 매우 많을거같은문제..

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] array = new int[N][N];

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

        for(int i=1 ; i<N ; i++){
            for(int j=0; j<=i ; j++){
                if(j==0){
                    array[i][0] +=array[i-1][0];
                }else if(j==i){
                    array[i][j] +=array[i-1][j-1];
                }else{
                    array[i][j] +=(array[i-1][j-1]>=array[i-1][j])?array[i-1][j-1]:array[i-1][j];
                }
            }
        }
        int max = 0;
        for(int i=0; i<N ; i++){
            max= (max>=array[N-1][i])?max:array[N-1][i];
        }
        System.out.println(max);
    }
}

정답은 맞았지만 최적화가 필요해보인다.
dp문제는 조금 다르게 생각해보면 정말 짧게 혹은 가볍게 코드를 짤수있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = i; j >= 0; j--) {
                int value = Integer.parseInt(st.nextToken());

                if (j == 0) {
                    dp[j] = dp[j] + value;
                } else if (j == i) {
                    dp[j] = dp[j - 1] + value;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]) + value;
                }
            }
        }

        int max = 0;
        for (int x : dp) max = Math.max(max, x);
        System.out.println(max);

    }
}

기존 코드와 달라진점은 메모리라고 볼 수 있겠다.
1차원 배열만 할당하여 모든 값을 저장할 필요가 없는 문제긴 했다.