[BOJ] BOJ 11660번 '구간 합 구하기 5' (Java)

[백준 11660 구간 합 구하기 5] 

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

[접근 방식]

합을 구하는 과정에서 단순 누적 방식을 사용한다면, 시간 초과 오류가 발생한다.

단순 누적 방식을 이용하는 경우에서, 최악의 경우는 "(1, 1) ~ (1024, 1024)" 까지의 누적합을 100,000 번 구하는 것이다.

이 경우를 고려한다면, M = 100,000 / N = 1,024 이고,  " M×N^2 = 100000 × 1024 × 1024 = 100,000 × 1,048,576 ≈ 10^11" 이다. 이 계산횟수는 시간 초과를 유발한다.

 

이 경우 최악의 시간 복잡도는 'M x O(N^2)' 가 된다.

 

따라서 누적합을 미리 계산해 놓아 계산 하는 방식을 채택했다.

 

표에서 임의의 좌표 (x, y) 에 대해 (1, 1) ~ (x, y) 의 합을 sum_arr[x][y] 에 저장해놓는 별도의 2차원 배열로 문제를 해결하고자 한다.

 

이 경우 시간 복잡도는 'O(N^2 + M)' 을 따른다.

 

[Java 코드]

/**
 * BOJ_11660 구간 합 구하기 5
 * https://www.acmicpc.net/problem/11660
 * keyword - 
 */

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

public class Main {

  static int N, M;
  static int[][] arr;
  static int[][] sum_arr; // (1, 1) ~ (x, y) 까지 합을 저장


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

    arr = new int[N + 1][N + 1];
    sum_arr = 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());
        sum_arr[i][j] = (sum_arr[i][j - 1] + sum_arr[i - 1][j] - sum_arr[i - 1][j - 1] + arr[i][j]);
      }
    }

    //x -> 행 , y -> 열
    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int[] start = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
      int[] end = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
      System.out.println(getSum(start, end));
    }
  }

  static int getSum (int[] start, int[] end) {
    
    int x1 = start[0];
    int y1 = start[1];
    int x2 = end[0];
    int y2 = end[1];
    
    int result = sum_arr[x2][y2] - sum_arr[x1 - 1][y2] - sum_arr[x2][y1 - 1] + sum_arr[x1 - 1][y1 - 1];
    return result;
  }
}

 

[Rewind]

1. 어려웠던 점

- (1, 1) ~ (x, y) 누적합을 미리 저장해 놓은 배열을 사용하는 것이 과연 DP 인것인가? 에 대한 고민

 

2. 알게된 점 

- DP 의 본질인 작은 계산을 미리 저장해 놓아(메모이제이션) 동일한 계산을 반복하지 않게 하는 것에 해당 방식이 대응된다. 또한, DP 의 큰 특징인 점화식의 성질도 띄고 있음으로 미리 계산해 놓은 누적합을 사용하는 방식은 DP 해결방식에 해당한다고 볼 수 있다.

 

3. 개선방안 

- 다양한 DP 문제에 대해 알아보아야 한다.

- 문제 조건에 시간 복잡도를 적용하여 문제 해결 방식을 빠르게 찾아야 한다.