[Baekjoon] 백준 11660 구간 합 구하기 5 (S1^ / 누적합) - Java

링크

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

11660번: 구간 합 구하기 5

 

 

 

 

문제 해석

N * N 크기의 표에서 (x1, y1)부터 (x2, y2)까지 합을 구하라

 

 

입력
첫 번째 줄 : N M
  N : 표의 w, h
  M : 찾을 횟수
N개 줄
  표 정보 표기
M개 줄 : x1 y1 x2 y2
  

출력
M줄 만큼 구간 합 구하기

 

 

 

 

풀이 & 코드 해석

이 문제는 첫 번째 한 행 또는 한 열씩 누적합을 구한 후, 반복을 통해서 구할 수 있습니다. 

(각 줄에 대한 누적합이 별도로 존재)

 

이 방법은 구간 합 구하기 4문제와 매우 유사한 풀이법을 가지게 됩니다.

 

 

 

조금 더 심화적인 방법으로는 2차원 배열의 누적합을 구한 후 누적합 배열을 사용하여 문제를 풀 수 있습니다.  

 

해당 방법은

1) 누적합 구하기

2) 결과 값 계산하기

와 같은 순서로 진행됩니다.

 

 

 

1) 누적합 구하기

문제의 입력 예시를 통해서 설명드리도록 하겠습니다.

 

A[][] 배열을 이용하여 누적합을 구할 S[][] 배열을 완성시켜야 합니다.

 

 

S[][] 배열의 각 위치의 값은 

S[i][j] = S[i][j - 1] + S[i - 1][j] + A[i][j] - S[i - 1][j - 1]

와 같은 식으로 구할 수 있습니다.

 

 

가령 S[2][2] 위치의 값을 구하기 위해서는,

S[2][1](노란색)과 S[1][2]의 값(파란색), 그리고 현재 위치인 A[2][2]를 더하면 됩니다.

 

이 때 S[1][1](초록색)은 노란색 부분의 누적합과, 파란색 부분의 누적합에 모두 포함되게 됩니다.

(S[1][1]은 S[2][1]과 S[1][2]를 더하면 두 번 포함 됨)

 

따라서 한 번 값을 빼줘야 하기 때문에 S[1][1]을 빼게 됩니다.

 

 

동일한 방법을 전체 배열을 돌면서 수행하면 누적합 배열 S[][]가 완성됩니다.

 

 

 

2) 결과 값 계산하기

x1, y1, x2, y2를 이용하여 우리가 원하는 구간의 구간합을 구하는 것이 최종 목표입니다.

 

S[x2][y2]를 기준으로 포함되지 않는 부분을 빼는 연산을 수행한다면 구할 수 있습니다.

 

 

마찬가지로 2 2 3 4 예시를 통해 살펴보면

S[3][4]를 기준으로 하여 포함되지 않는 S[1][4](노란색)와 S[3][1](초록색)를 뺀다면 결과를 구할 수 있을 것입니다.

 

이때 S[][]를 구할 때와 동일하게 파란 부분이 중복되어 들어가는 현상이 발생합니다.

(S[1][1]이 두 번 빠짐)

 

따라서 최종적으로 파란 부분인 S[1][1]을 한 번 더해주면 됩니다.

 

 

 

 

코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] a = new int[N + 1][N + 1];
		int[][] s = 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++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 누적 합 구하기
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				s[i][j] = s[i][j - 1] + s[i - 1][j] + a[i][j] - s[i - 1][j - 1];
			}
		}
		
//		print(s);
		
		// 구간 합 구하기
		for (int tc = 0; tc < M; tc++) {
			st = new StringTokenizer(br.readLine());
			int sr = Integer.parseInt(st.nextToken());
			int sc = Integer.parseInt(st.nextToken());
			int er = Integer.parseInt(st.nextToken());
			int ec = Integer.parseInt(st.nextToken());
			
			int answer = s[er][ec] - s[sr - 1][ec] - s[er][sc - 1] + s[sr - 1][sc - 1];
			System.out.println(answer);
		}
		
	}
	
	public static void print(int arr[][]) {
		System.out.println();
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
	}

}

 

 

 

 

발생한 문제 & 해결 방안

 

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java