[알고리즘] Q004 구간합 (2차 배열)

 

코딩테스트에 자주 등장하는 2차배열 구간합 관련 문제

package Quiz;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringBufferInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q004_구간합구하기2 {
	public static void main(String[] args) throws IOException {
		//NxN개 수가 NxN크기의 표에 채워져있다. (X1,Y1)부터 (X2,Y2)까지 수의 합구하기(X:행, Y:열, 제한시간: 1초)
		//입력값 
		//1: 표의 크기 N과 합을구하는 횟수 M (1<=N<=1024, 1<=M<=100000) 
		//2 째 줄부터 N개의 줄에는 표에 채워져야 하는 수가 1행부터 차례대로 주어짐 
		//3.다음 M개의 줄에는 4개의 정수 X1,Y1, X2,Y2가 주어지며, (X1,Y1)부터 (X2,Y2)까지 합을 출력해야함
		
		//분석하기 
		//2차원 구간합 배열 D[X,Y]의 정의 
		//D[X,Y] = 원본 배열의 (0,0)부터 (X,Y)까지의 사각형 영역안에 있는 수의 합
		//D[i,j]를 채우는 공식 : D[i,j] = D[i-1,j] + D[i,j-1] - D[i-1, j-1] +D[i,j];
		
		//질의 X1,Y1 부터 X2,Y2까지의 구간합 구하는 공식 : D[X2,Y2] - D[X1-1,Y2] - D[X2,Y1-1] + D[X1-1, Y1-1];
		
		/* 슈도코드 작성
		 * 
		 * N(배열크기) M(질의횟수) 저장
		 * 
		 * for(N만큼 반복하기)
		 * 	for(N만큰 반복하기)
		 * 		원본배열 저장하기
		 * 		배열구간합 저장하기
		 * 
		 * for(M만큼 반복하기)
		 * 	질의 구간합 출력하기 
		 * */
		
		/* 테스트 값 1
 2 4 
 1 2 
 3 4
 1 1 1 1 
 1 2 1 2 
 2 1 2 1 
 2 2 2 2 
			 
		   테스트 값 2 
 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 
 
		 * */
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken()); // 배열크기 
		int M = Integer.parseInt(st.nextToken()); // 반복횟수
		int arrN[][]   = new int[N+1][N+1]; // 배열
		int dSum[][] = new int[N+1][N+1]; // 구간합
		
		//배열 + 구간합배열 생성
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=1; j<=N; j++) {
				arrN[i][j]   = Integer.parseInt(st.nextToken()); //배열 생성
				System.out.println("arrN["+i+"]["+j+"]: " + arrN[i][j]);
				
				dSum[i][j]   = dSum[i-1][j] + dSum[i][j-1] - dSum[i-1][j-1] + arrN[i][j]; //배열구간합 생성	
				System.out.println("dSum["+i+"]["+j+"]: "+ dSum[i][j]);
			}
		}
		
		System.out.println("arrN: "+ Arrays.deepToString(arrN));
		System.out.println("arrN: "+ Arrays.deepToString(dSum));
		
		//구간합 구하기 
		for(int i=0; i<=M; i++) {
			st = new StringTokenizer(bf.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());
			
			System.out.println(dSum[x2][y2] - dSum[x1-1][y2] - dSum[x2][y1-1] + dSum[x1-1][y1-1]);
		}
	}
}

/*
[0, 1, 2, 3, 4], 
[0, 2, 3, 4, 5], 
[0, 3, 4, 5, 6], 
[0, 4, 5, 6, 7]


[0, 1,   3,  6, 10], 
[0, 3,   8, 15, 24], 
[0, 6,  15, 27, 42], 
[0, 10, 24, 42, 64]
*/

---

1차 배열

/*문제: 수 N개가 주어졌을때 i번째 수까지의 합을 구하는 프로그램을 작성하시오
 *1번째 줄에 수의개수 N (1<= N <= 100,000), 합을 구해야하는 횟수 M (1<= N <= 100,000)
 *2번째 줄에 N개의 수가 주어진다. 각 수는 1000보다 작거나 같은 자연수다.
 *3번째 줄부터는 M개의 줄에 합을 구해야하는 구간 i와 j가 주어진다. 
 * 
 * 
 ******************************************
 * e.g) 인덱스(i)|0 |1 |2 |3 |4 |5
 *  --------------------------
 *   배열 A |15 |13 |10 |7 |3 |12
 *     합 배열 S |15 |28 |38 |45 |48 |60
 * 
 * # 합배열 S를 만드는 공식
 * S[i] = S[i-1] + A[i]
 * 
 * # 구간합을 구하는 공식
 * S[j]- S[i-1] //i~j까지 구간합 
 * 
 * */

 

int N        ;          	//N개의 개수
		int M        ; 			//합을 구해야하는 횟수
		int[] num    ; 	//수의 개수
		long[] numSum ; //구간합배열 초기화

		int rs = 0; //총구간합 
		
		//Scanner sc = new Scanner(System.in);
		BufferedReader  bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		//1번째 입력라인 : N,M
		N   = Integer.valueOf(st.nextToken());
		M   = Integer.valueOf(st.nextToken());
		num = new int[N];
		numSum = new long[N+1];
		
		//2번째 입력라인 : 수
		st = new StringTokenizer(bf.readLine());
		//구간합 배열 생성 (구간은 1부터 시작임)
		for (int i = 1; i <= N; i++) {
			numSum[i] = numSum[i-1] + Integer.valueOf(st.nextToken()); //이전구간합S	 + 현재값A
		}
				
		System.out.println("구간합 최종 : " + Arrays.toString(numSum));
		
		//3번째~ 입력라인 : 구간반복 횟수 
		for (int k = 0; k < M; k++) {
			int i, j; // 구간초기화

			st = new StringTokenizer(bf.readLine());
			i = Integer.valueOf(st.nextToken());
			j = Integer.valueOf(st.nextToken());			
						
			//구간합 구하기
			rs += numSum[j] - numSum[i-1];	
			
			System.out.println("정답 :" + (numSum[j] - numSum[i-1]));
		}
		
		System.out.println("정답(총합) :" + rs  );

 

728x90

2차 배열

/* 문제 : N x N개의 수가 N x N 크기의 표에 채워져있다. 좌표 (x1,y1) 부터 (x2,y2)까지의 합 구하기 
 * 
 * 1번째 줄 : 표의 크기 N과 합을 구해야 하는 횟수 M (1<=N<=1024, 1<= M <=100,000)
 * 2번째 줄 : N개의 줄에 표에 채워져있는 수가 1행부터 차례대로 주어진다. 
 * 
 * 2차원 구간합 : D[x][y] = 원본배열 (0,0)부터 (x,y)까지의 사각형 안의 수의 합
 * 2차원 구간합 배열생성 공식 : D[x][y] = D[x][y-1] + D[x-1][y] + A[x][j] - D[x-1][y-1]
 * 2차원 구간합 공식 : sum = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
 * 
 * */

int  N ; 
		long M ;
		int[][] D ;
		int rs = 0;
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.valueOf(st.nextToken()); //표 크기초기화
		M = Integer.valueOf(st.nextToken());
		D = new int[N+1][N+1]; //구간합배열 초기화 
		
		//구간합 구하기
		for (int x = 1; x <= N; x++) {
			st = new StringTokenizer(bf.readLine());
			for (int y = 1; y < D.length; y++) {
				//구간합배열 값생성
				//D[x][y] = D[x][y-1] + D[x-1][y] + A[x][j] - D[x-1][y-1]
				D[x][y] = D[x][y-1] + D[x-1][y] - D[x-1][y-1] + Integer.valueOf(st.nextToken());				
			}
			System.out.println("구간합 : "+ Arrays.toString(D[x]));
		}
		
		//답출력
		for (int k = 1; k <= M; k++) {
			st = new StringTokenizer(bf.readLine());

			int x1 = Integer.valueOf(st.nextToken());
			int y1 = Integer.valueOf(st.nextToken());
			int x2 = Integer.valueOf(st.nextToken());
			int y2 = Integer.valueOf(st.nextToken());
			
			//sum = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
			
			System.out.println("정답 : "+ ( D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]));
		}