코드트리 - 슬라이딩 윈도, 누적합, prefix max 기법, 최적화

문제 링크

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-best-place-of-13-2/description

최고의 13위치 2 설명 | 코드트리

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

public class Main {
    static int N;
    static int[][] board;
    static int[][] ps;

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

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

        // 1*3 전처리
        for(int i = 1; i<=N; i++){
            int cur = board[i][1] + board[i][2] + board[i][3];
            ps[i][1] = cur;
            for(int j = 2; j<=N-2; j++){
                cur -= board[i][j-1];
                cur += board[i][j+2];                
                ps[i][j] = cur;
            }
        }

        int ans = 0;
        // 다른행, 위쪽에서의 최대
        int upMax = 0;
        for(int i = 1; i<=N; i++){
            // 같은행, 왼쪽에서부터의 최대
            int[] leftMax = new int[N+1];
            for(int j= 1; j<=N-2; j++){
                leftMax[j] = Math.max(j>=2 ? leftMax[j-1] : 0, ps[i][j]);
            }

            for(int j = 1; j<=N-2; j++){
                // 1. 두 윈도가 서로 다른 행에 있을땐 위쪽기준 max값에 현재값 더한거 비교
                ans = Math.max(ans, upMax + ps[i][j]);
                // 2. 두 윈도가 같은 행에 있을땐 왼쪽기준 max값에 현재값 더한 거 비교
                if(j >= 4){
                    ans = Math.max(ans, leftMax[j-3] + ps[i][j]);
                }
            }

            // 행이 다를때 쓸 위쪽기준 최대값 갱신
            // -> 한 행 통째로 sum값 죄다넣고 최대로
            for(int j = 1; j<=N-2; j++){
                upMax = Math.max(upMax, ps[i][j]);
            }
        }
        
        System.out.print(ans);
    }
}

사고의 흐름 및 문제 정리

처음에는 두개의 슬라이딩 윈도니까 그냥 2차원 누적합 구한다음에 적당히 시작위치 찾아가지고 비교하면 되겠다고 생각했다.

근데 문제를 오해를 해서 무조건 2번째가 다른 행에 있다고 착각해서 WA 났고, 같은 행에 있다고 하고 대충 abs로 서로 시작점 위치 비교해서 3칸 확보 안되면 스킵하게 하니까 되긴되는데 시간복잡도가 사실상 O(N^4)라서 AC긴 하지만 납득할 수 없었다.

 

누적합의 누적을 하던지 아니면 덱같은거 크기 고정해놓고 최대값, 최소값 유지하면서 갱신시키는거처럼 현재 max값을 저장해서 유지하면서 갱신하기?? 어차피 최대를 구하는 거고 단조적이니까 괜찮을 거 같았다.

-> 두번째 직사각형 관점에서는 첫번째의 최적값만 보면 된다.

 

풀이 : Prefix max

그러면 이걸 어떻게 압축하느냐?? 일단 다행히도 윈도 크기는 1*3이다. 

따라서 행단위로 3칸짜리 합을 계산한 prefix sum 배열을 구해놓는다. 시작점이 4 넘어가면 (1-based) 이므로 슬라이딩윈도로 빠르게 구하는 방식으로 일단 전처리를 한다.

 

문제의 목표는 두 구간의 합이 최대로 되는 값을 찾는 것이고 그 전꺼의 최대 + 현재값을 한게 최대라면 갱신하면 된다는 것이다.

이 문제에서는 가능한 상태의 경우가 2개이다.

 

1) 같은 행 안에서의 구간 2개 

-> 이는 이전 열 idx까지의 최대값을 저장하는 leftMax 배열을 생성해서 미리 계산한다. 

-> 그리고 시작점 기준이므로 j-3 인덱스의 leftMax 값에 현재 위치 합을 더하면 현재까지의 최대 합이 된다.

 

2) 다른 행 안에서의 구간 2개

-> 이건 어차피 다른 행이라서 이전 행까지의 최대값(upMax)을 가져오면 되니까

한 행의 prefix sum 배열값을 다 보면서 갱신한다. 

 

upMax는 그냥 int 변수로 유지하고 순차 DP 구조를 유지하기 위해 제일 마지막에 계산한다.

-> 왜냐하면 마지막에 계산해야 첫번째 행을 연산할때 0으로 유지되어 올바른 값을 띄게 된다.