[백준] 단계별로 풀어보기(단계:16, 누적합,JAVA)11660번, 구간 합 구하기

문제 링크

11660번: 구간 합 구하기 5

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

누적합이란?

입력되는 값들의 누적합 값을 따로 저장하여 필요에 따라 사용하는 알고리즘입니다.

 

예를 들어 1 5 4 36 8이 입력되었을 때 누적합 값을 저장한 배열을 표로 표현하면

	1	5	4	36	8
누적합	1	6	10	46	54

이 문제에 핵심은

1. 입력되는 N × N의 수에서 (x1, y1), (x2, y2) 구간의 합을 구합니다.

 

사용한 배열

 

DP[][] : 누적합 저장 배열

 

num[][] : N × N의 수를 저장한 배열

 

점화식

 

누적합을 이용하여 연속하는 수 범위에 합을 구하는 방법(i : 시작 범위, j : 끝 범위)

해당 범위 합 = DP[j] - DP[i-1]

 

예제입력 1에서 N × N의 수를 표로 표현하면(빨간색은 (x1, y1) , (x2, y2) 구간)

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

 

해당 범위의 값을 그냥 더해도 되지만 이 문제에서는 시간초과가 발생합니다.

그래서 누적합을 따로 저장하여 이용하였습니다.

 

예제입력 1에서 N × N의 수에 누적합을 나타내면

1	3	6	10
2	5	9	14
3	7	12	18
4	9	15	22

 

N × N의 행마다 누적합을 모두 더하면 해당 구간의 모든 수의 합을 구할 수 있습니다.

예제입력1에서는

 

(2,2) ~ (2,4)

누적합 = DP[2][4] - DP[2][1] = 12

 

(3,2) ~ (3,4)

누적합 = DP[3][4] - DP[3][1] = 15

 

12 + 15 = 27

결과적으로 구간의 합은 27이 결과로 출력됩니다.

 

※만약 x1의 값과 x2의 값이 동일하면

같은 행에 존재하는 것으로 판단할 수 있어서 따로 구분해서 구해주어야 합니다.

 

예제입력 1에서 (2, 2), (2, 4)이 구간이면

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

 

점화식은 = DP[x2][y2] - DP[x1][y1-1]

 

누적합 = DP[2][4] - DP[2][1] = 12

 

결과를 구할 수 있습니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N과 M 및 N×N의 수, (x1,y1) , (x2,y2)를 저장합니다.

2. N × N에 대한 누적합을 DP[][]에 저장합니다.

3. 입력되는 구간의 범위를 행마다 누적합을 모두 더해서 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 N×N개의 수와 구간을 분리하였습니다.
• N×N개의 수에 대한 누적합을 DP[][]에 저장하였습니다.
• 입력되는 구역별 구간합을 구하는 cal함수를 만들었습니다.
• BufferedWriter에 cal함수에 반환된 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 x1==x2일 때와 그 이외의 경우를 나누어 계산하였습니다.
• cal함수는 각 행의 누적합의 합을 이용하여 구간의 합을 구하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int N,M;
	static int[][] num,DP;	//N×N수 저장 배열, 누적합 저장 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
        	//------입력값 저장 및 배열 초기화------
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		num = new int[N+1][N+1];
		DP = 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++) {
				num[i][j] = Integer.parseInt(st.nextToken());
				DP[i][j] = DP[i][j-1] + num[i][j];	//누적합 저장
			}
		}
		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 result = cal(x1,y1,x2,y2);	//구간 범위 구하는 함수 실행
			bw.write(result + "\n");		//구간 합 BufferedWriter 저장
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//행의 누적합을 이용하여 구간의 합을 구하는 함수
	static int cal(int x1, int y1, int x2, int y2) {
		int sum = 0;
		if(x1 == x2)		//x1==x2일 때에는 행이 동일하기 때문
			sum = DP[x2][y2] - DP[x1][y1-1];
		else {
        		//행마다 누적합 더하는 연산
			for(int i=x1;i<=x2;i++)
				sum += DP[i][y2] - DP[i][y1-1];
		}
		return sum;		//구간의 합 반환
	}
}