코드트리 [자바 java] 정수 사각형 최대 합

https://www.codetree.ai/missions/2/problems/maximum-sum-path-in-square?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

행렬에서 1,1에서 n,n까지 가는데 거쳐간 위치에 있던 숫자의 합이 최대가 되도록 하는 문제이다.

 

나는 dp배열을 하나 더 만들었다. 이는 1,1에서 dp각각의 칸까지 이동할 때 경로상에 있는 숫자를 더한 최대값을 의미한다. 제일 위 칸은 위에서 오는 경우가 없다. 왼쪽에서 오는 경우밖에 없으니까 왼쪽 값에 해당 칸의 arr값을 더한 것이 최대가 된다. 가장 왼쪽 줄도 마찬가지다 . 이 칸은 왼쪽이 없으니까 위에서 오는것이 최대값이 된다.  

반면, 가운데 칸은 왼쪽 칸도 있고, 위쪽 칸도 있으니까 둘의 값을 비교해보아야 한다. 비교 결과, 왼쪽이 더 크므로 가운데 칸의 dp값은 6이 된다.

 

 이 문제에서 주의할 점은 배열을 만들 때 arr[n][n]이 아닌 arr[n+1][n+1]이런 식으로 만들어야 한다는 점이다. 왜냐하면 왼쪽, 위쪽 값이 없는 경우를 따지지 않아도 되기 때문이다. (값이 없으면 격자를 넘어가서 에러가 나는 것이 아니라 그냥 그 곳의 값이 0이니까 Math.max를 쓰면 자동으로 무시된다.)

 

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

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());

        StringTokenizer st;


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

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

        for(int i = 1;i<=n;i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 1;j<=n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());

            }
        }

       //윗줄부터 차례로 dp값 채우기
       //for문 j부터 시작하는 것 주의

        for(int j =1;j<=n;j++){
            for(int i = 1;i<=n;i++){
                dp[i][j] = arr[i][j] + Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }

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

    }
}