[코드트리 챌린지] 정수 사각형 최대 합

문제 : 정수 사각형 최대 합

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

 

문제

N×N 행렬이 주어졌을 때, (1,1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최대로 하는 프로그램을 작성해보세요.3 ≤ n ≤ 100,000

 

-1,000 ≤ 주어지는 수 ≤ 1,000

 

 

사실 실력진단에서 유사한 문제가 나왔는데 DFS 방식으로 풀려다가 시간이 부족했고, 이 문제는 BFS 방식으로 풀었다.

 

풀이는 아래와 같다.

1. DP테이블에 초기 좌표 0, 0에는 입력된 0,0의 값을 넣어준다.

2. 이후 이동 가능한 곳을 방문하며, DP테이블에 값을 갱신해준다.

3. 이 때 이미 방문했다면 해당 좌표는 queue에 넣어주지 않고, 방문하지 않은 경우에 방문 체크와 함께 queue에 값을 넣어준다.

 

시간복잡도를 계산하면

1. 전체를 순회하므로 O(N^2)

 

코드는 아래와 같다

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
    static int n;
    static int[][] map;
    static int[][] dp;

    static boolean[][] visit;

    static int[] dy = {0, 1};
    static int[] dx = {1, 0};

    static void input() throws IOException{

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        visit = new boolean[n][n];
    }

    static void pro() {
        bfs();
        System.out.println(dp[n - 1][n - 1]);
    }

    static void bfs() {

        Deque<int[]> que = new ArrayDeque<>();
        que.add(new int[]{0, 0});
        visit[0][0] = true;
        dp[0][0] = map[0][0];

        while (!que.isEmpty()) {

            int[] cur = que.poll();
            for (int i = 0; i < 2; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny == n || nx == n) continue;
                dp[ny][nx] = Math.max(dp[ny][nx], dp[cur[0]][cur[1]] + map[ny][nx]);
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                que.add(new int[] {ny, nx});
            }

        }

    }

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

    }

}