[백준, BOJ 1749] 점수따먹기 (java)

https://www.acmicpc.net/problem/1749

1749번: 점수따먹기

728x90

---

메모리: 20,324 KB , 시간: 328 ms

사용 알고리즘: 누적 합, 부르트포스 알고리즘, 다이나믹 프로그래밍

 

내생각

완탐을 돌리면 시간 복잡도가 $O(N^4)$로 16억이 넘어가서 시간초과일 거라고 생각했다.

(다른 답들을 보니까 완탐 돌려도 되긴 하나보다..)

 

근데 아무리 생각해도 16억이 넘어가는 범위인데 정답만 받으면 의미가 없을 거라고 생각해서 머리 쥐어짜다가 결국 해결법을 찾지 못해서 여러 풀이를 찾아봤다.

(많은 풀이들이 다 완탐 돌려서 탐탁치 않았음..)

 

겨우 $O(N^3)$으로 푸신 분의 해설을 보았고, 겨우 이해해서 풀었다.

 

정리해보자면,

일단 가로줄 별로 누적합을 저장해서 sum배열에 저장한다.

2중 for문(i, j)을 돌면서 현재 줄의 포함 범위를 정해준다. (k번째 줄의 i + 1 ~ j까지 합 = sum[k][j] - sum[k][i])

그 안에 for문(k)을 한 번 더 돌면서, 위에서 아래로 내려가며

윗줄의 합을 더해주는게 현재 줄 입장에서 더 크다면, 더해주고

윗줄의 합을 더해주지 않는게 현재 줄 입장에서 더 크다면 더해주지 않는다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

        final int MIN = -400_000_000;

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N + 1][M + 1];
        int[][] sum = new int[N + 1][M + 1]; // 각 행에 대한 누적합만 저장
        int maxNum = MIN;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                sum[i][j] = sum[i][j - 1] + arr[i][j];
                maxNum = Math.max(maxNum, arr[i][j]);
            }
        }

        int result = MIN;
        if(maxNum <= 0) { // 양수가 하나도 없다면
            result = maxNum; // 가장 큰 칸만 포함
        }
        else {
            int max, tmp;
            for (int i = 1; i <= M; i++) { // i + 1열부터
                for (int j = i; j <= M; j++) { // j열까지 포함
                    max = MIN;
                    for (int k = 1; k <= N; k++) { // 1~N까지 검사
                        // 위의 행을 합치는게 좋을지, 현재 행만 두는게 좋을지 검사
                        tmp = sum[k][j] - sum[k][i]; // 현재 행
                        max = Math.max(max + tmp, tmp);
                        result = Math.max(result, max);
                    }
                }
            }
        }

        System.out.println(result);
    }
}