소프티어

import java.io.*;

import java.util.*;




public class Main {




  static int n, ans;

  static int[][] map;

  static long[][][] dp;  //마지막에 값이랑, 쿨러포인트

  static final int[] dr = {1, 0};

  static final int[] dc = {0, 1};

   

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st;

    n = Integer.parseInt(br.readLine());

    map = new int[n+1][n+1];

    dp = new long[n+1][n+1][2];

    for(int i=1; i<=n; i++) {

      st = new StringTokenizer(br.readLine());

      for(int j=1; j<=n; j++) {

        map[i][j] = Integer.parseInt(st.nextToken());

      }

    }

    /*

    (0,0)~(n-1,n-1) 까지 오른쪽/아래 방향으로만 이동가능.

    sol1) 일단 가는 길은 완전탐색(DFS)을 하고, 가면서 가장 큰 값을 갱신한다.

    완탐하니까 시초난다. 

    sol2) dp로 풀어서 현재까지의 최댓값을 갱신하면서 탐색한다

    */

    for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                // 현재 값까지 더해서 나온 값을 가지고 따져야 한다
                int a = dp[i-1][j][1];	//내 기준 위까지 오는데 가장 컸던 값
                int b = dp[i][j-1][1];	//내 기준 왼쪽까지 오는데 가장 컸던 값
                int c = map[i][j];	//현재 값
                int tmp1 = 0, tmp2 = 0;

                if(a<c) {	//현재값이 더 크면 기존에 두배한걸 하나 빼주고 내 위치에 스프링쿨러(2배)
                    tmp1 = dp[i-1][j][0] - a + 2*c;
                } else {	// 아니면 기존까지 최댓값에 내 값 한번 더함.
                    tmp1 = dp[i-1][j][0] + c;
                }
                if(b<c) {
                    tmp2 = dp[i][j-1][0] - b + 2*c;
                } else {
                    tmp2 = dp[i][j-1][0] + c;
                }
                
                if(tmp1 >= tmp2) {	//위쪽으로 오는게 더 크면 tmp1
                    dp[i][j][0] = tmp1;
                    dp[i][j][1] = (a<c) ? c : a;	//스프링쿨러있는 좌표값 재설정
                } else {
                    dp[i][j][0] = tmp2;	//아래쪽으로 오는게 더 크면 tmp2
                    dp[i][j][1] = (b<c) ? c : b;
                }
  
                // for(int ii=1; ii<=n; ii++) {
                //     for(int jj=1; jj<=n; jj++) {
                //     System.out.print(dp[ii][jj][0] + " ");
                //     }
                //     System.out.println();
                // }
                // System.out.println();
            }
        }

    System.out.println(dp[n][n][0]);

  }

   

}

생각하기로는 메모리랑 시간이 테케 중에서 젤 오래걸리는거보니 경계값쪽에서 틀리는 것 같기도 한데요. 모르겠습니다 ,,