[BOJ][파이썬, 자바]11660 구간 합 구하기5

반응형

✨ 문제 링크

 

Idea : 누적합을 이용한 부분합 구하기(행 마다 누적합 구한 후 구간합으로 자르기)

 

이차원배열의 내용들을 쭉 편 후 일차원배열에 누적합을 구한 후 사용하려 했으나 그렇게 하면 시작부분이 첫번 째 열이 아닐시에 빠지는 부분이 있다

 

예를 들어, 아래와 같은 입력 예제에서 위와 같은 방법을 사용하면

(2, 2)에서 (3, 4)에 해당하는 구간을 구하면 3 + 4 + 5 + 4 + 5 + 6이 나와야하나 처음 언급한 방식으로 접근하면 3까지 포함된다.

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

따라서 행 마다의 누적합을 구한 후 입력에 따라 구간합으로 짤라서 사용한다

자바 코드

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

public class BOJ11660 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;

	static int N, M;
	static int [][] accums;
	static int x1, x2, y1, y2;

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		accums = new int[N][N + 1];
		
// 행별로 누적합 저장
		for(int r = 0; r < N; r++) {
			int cnt = 1;
			tokens = new StringTokenizer(input.readLine());
			for(int c = 0; c < N; c++) {
				accums[r][cnt] += accums[r][cnt - 1] + Integer.parseInt(tokens.nextToken());
				cnt ++;
			}
		}

// 입력에 맞춰 구간합으로 자른 후 출력
		for(int tc = 0; tc < M; tc++) {
			tokens = new StringTokenizer(input.readLine());
			x1 = Integer.parseInt(tokens.nextToken());
			y1 = Integer.parseInt(tokens.nextToken());
			x2 = Integer.parseInt(tokens.nextToken());
			y2 = Integer.parseInt(tokens.nextToken());

			int start = y1-1;
			int end = y2;
			int sum = 0;
			for(int i = x1 - 1; i <= x2 - 1; i++) {
				sum += (accums[i][end] - accums[i][start]);
			}
			output.append(sum + "\\n");
		}
		System.out.println(output);
 }
}

파이썬 코드

import sys
sys.stdin = open("input.txt", "r")

N, M = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(N)]
accums = [[0] * (N + 1) for _ in range(N)]

for r in range(N):
    for c in range(N):
        accums[r][c+1] = accums[r][c] + mat[r][c]

for _ in range(M):
    x1, y1, x2, y2 = map(int ,input().split())
    sum = 0
    start = y1 -1
    end = y2
    for r in range(x1 - 1, x2):
            sum += accums[r][end] - accums[r][start]
    print(sum)