백준 1749 JAVA : 점수따먹기

문제

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

1749번: 점수따먹기

풀이 예상

2차원 배열 안에서 누적합을 이용한 풀이

 

풀이방법 (접근 방법 & 시간복잡도)

2차원 배열 안에서의 누적합은 아래와 같이 구할 수 있다.

주황색 칸을 구하기 위해서 왼쪽, 위쪽 칸을 더하고 왼쪽 위 대각선 칸을 빼주면 된다. 식으로 나타내면

sum[i][j] = num +  sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]; //본인자리숫자 + 왼쪽칸 + 위쪽칸 -왼쪽위대각선칸

 

이렇게 해서 모든 칸을 더하면 이런 누적 합 배열이 완성된다. (예제)

각 칸은 [1][1] ~ [i][j] 까지의 모든 합을 더한 값을 의미한다.

 

여기서 주황색 칸만 구하려고 한다면

 

 

 

이 칸을 A

 

 

 

 

이 칸을 B

 

 

 

 

이 칸을 C

 

 

 

 

이 칸을 D라고 했을 때

 

 

 

구하려고 하는 곳 = A - B - C + D(겹치는 부분) 의 식이 만들어진다. 이를 이용해서 코드를 작성하면 아래와 같다.

 

시간복잡도 =>  O(N^3)

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] sum = new int[N+1][M+1]; //0,0 ~ i,j 직사각형의 합

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                int num = Integer.parseInt(st.nextToken());
                sum[i][j] = num + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]; //누적합
            }
        }
        
        int answer = Integer.MIN_VALUE;


        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                //하나씩 본다.

                for (int k = 0; k < i; k++) {
                    for (int l = 0; l < j; l++) {
                        int sumNumber =  sum[i][j] - sum[k][j] - sum[i][l] + sum[k][l];
                        answer = Math.max(answer, sumNumber);
                    }
                }

            }
        }

        System.out.println(answer);

    }
}

결과