백준 JAVA11 11660번 : 구간 합 구하기 5

Mention : 구간 합 구하기 시리즈, 이차원 배열 + 구간합😱

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	33466	15743	12251	46.169%

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제 입력 1

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력 1

27
6
64

예제 입력 2

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력 2

1
2
3
4

FirstTry

• 시간복잡도
  • O(N^2 + M)
  • O(1,048,576 + 100,000)
    • 1,148,576 → 약 0.01148 sec
  • 시간복잡도는 문제가 없어보이나, 시간초과가 났다 → 리팩토링

• 입력받은 값의 이차원 배열 예시

  [0, 0, 0, 0, 0]

  [0, 1, 2, 3, 4]

  [0, 2, 3, 4, 5]

  [0, 3, 4, 5, 6]

  [0, 4, 5, 6, 7]

• 이차원 합 배열 예시

  [0, 0, 0, 0, 0]

  [0, 1, 3, 6, 10]

  [0, 3, 8, 15, 24]

  [0, 6, 15, 27, 42]

  [0, 10, 24, 42, 64]

  • 포인트 : 문제에 답변하는 수식 만들기
    • sumTable [x2][y2] - sumTable[x1-1][y2] - sumTable[x2][y1-1] + sumTable [x1-1][y1-1] (두 번 빼주어서 한 번 더해줘야한다)

package prefixSum;

import java.util.Scanner;

public class P11660_prefixSum5 {

	public static void main(String[] args) {
		// N개의 수를 입력받는다. 횟수 M을 입력받는다.
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		// 입력받은 값의 이차원 배열을 생성한다.
		int[][] table = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				table[i][j] = sc.nextInt();
			}
		}
		// 이차원 합 배열을 생성한다.
		int[][] sumTable = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				{
					sumTable[i][j] = sumTable[i][j - 1] + sumTable[i - 1][j] - sumTable[i - 1][j - 1] + table[i][j];
				}
			}
		}
		// 이차원 합 배열을 통해 구간 합을 구한다.
		for(int i = 1; i<=M; i++) {
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			int x2 = sc.nextInt();
			int y2 = sc.nextInt();
			// 출력
			int result = sumTable[x2][y2] - sumTable[x1-1][y2] - sumTable[x2][y1-1] + sumTable[x1-1][y1-1];
			System.out.println(result);
		}
	}
}

리팩토링

package prefixSum;

import java.util.Scanner;

public class P11660_prefixSum5 {

	public static void main(String[] args) {
		// N개의 수를 입력받는다. 횟수 M을 입력받는다.
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		// 입력받은 값의 이차원 배열을 생성한다.
		// 이차원 합 배열을 생성한다.
		// 이차원 합 배열을 통해 구간 합을 구한다.
		int[][] table = new int[N + 1][N + 1];
		int[][] sumTable = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				table[i][j] = sc.nextInt();
				sumTable[i][j] = sumTable[i][j - 1] + sumTable[i - 1][j] - sumTable[i - 1][j - 1] + table[i][j];
			}
		}
		
		for(int i = 1; i<=M; i++) {
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			int x2 = sc.nextInt();
			int y2 = sc.nextInt();
			// 출력
			int result = sumTable[x2][y2] - sumTable[x1-1][y2] - sumTable[x2][y1-1] + sumTable[x1-1][y1-1];
			System.out.println(result);
		}
	}
}

• 입출력으로 BufferedReader, InputStreamReader, StringTokenizer를 사용하면 입출력 속도를 좀 더 빠르게 할 수 있을것으로 예측