[Java+Python]11660번, 구간 합 구하기 5

목차

 

누적 합

 

[Java+Python]11659번, 구간 합 구하기 4

[Java+Python]2559번, 수열

[Java+Python]16139번, 인간-컴퓨터 상호작용

[Java+Python]10986번, 나머지 합

[Java+Python]25682번, 체스판 다시 칠하기 2

 

문제

 

N×N개의 수가 N×N 크기의 표에 채워져 있다. 

(x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. 

(x, y)는 x행 y열을 의미한다.

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

여기서 (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. 배열의 크기 n과 구간 합을 구할 횟수 m을 입력받고 (n + 1) x (n + 1) 크기의 배열 table 생성 및 초기화
2. n번째 행과 열을 입력받으며 동시에 누적 합 계산해 table 배열 완성
   
   
   1. 이 경우 table[i][j] = table[i -1][j] + table[i][j - 1] -table[i - 1][j - 1]로 정해짐
   2. 왼쪽 대각선 위의 값을 빼주는 이유는 그렇지 않을 경우 중복으로 값이 더해지기 때문
3. 주어진 좌표(x1, y1, x2, y2)를 이용해 누적 합 계산
   
   
   1. 이 경우 누적합 sum = table[x2][y2] - table[x1 - 1][y2] - table[x2][y1 - 1] + table[x1 - 1][y1 - 1]로 정해짐
   2. 여기서도 마찬가지로 중복으로 값을 빼기 때문에 왼쪽 대각선 위의 값을 한 번 더해주어야 함
4. 적절한 방식으로 출력

왼쪽 대각선 위의 값을 처리하는 방식만 이해하면 나머지는 일차원 누적 합 계산과 다를 것이 없다는 것을 확인할 수 있다.

 

계속해서 구현 코드를 보자.

 

Java

 

package BackJoon;

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

public class Prob11660 {

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

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] table = 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++) {
				table[i][j] = Integer.parseInt(st.nextToken());
				table[i][j] += table[i - 1][j] + table[i][j - 1] - table[i - 1][j - 1];
			}
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());

			int sum = table[x2][y2] - table[x1 - 1][y2] - table[x2][y1 - 1] + table[x1 - 1][y1 - 1];
			sb.append(sum).append("\n");
		}

		System.out.println(sb.toString());
	}
}

 

시간 단축을 위해 StringBuilder를 이용해 문자열을 생성 후 출력했다.

 

Python

 

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())

table = [[0] * (n + 1)] * (n + 1)

for i in range(1, n + 1):
    table[i] = [0] + list(map(int, sys.stdin.readline().split()))
    for j in range(1, n + 1):
        table[i][j] += table[i - 1][j] + table[i][j - 1] - table[i - 1][j - 1]

for i in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().rstrip().split())
    sum = table[x2][y2] - table[x1 - 1][y2] - table[x2][y1 - 1] + table[x1 - 1][y1 - 1]
    print(sum)

동일한 로직을 파이썬으로. 다만 출력은 그때그때 해주는 방식으로 구현했다.

 

Performance

 

파이썬 로직이 최적화가 되어있지 않은지 자바보다 성능이 좋지 않았다.

 

자바 코드처럼 결과를 모아서 출력하도록 하면 미세하게 성능이 개선되기는 했으나(952ms → 904ms)

 

굳이 코드를 올리진 않았다.