<Baekjoon> #11659 #11660 구간 합 구하기

Google 아니고 Joogle·2022년 8월 3일

Baekjoon

목록 보기

43/47

💡#11659 구간합4

Idea

구간 합 구하기 문제의 핵심은 누적합을 Memoization 기법을 사용하여 해결하는 것이다
N과 M이 최대 100,000이기 때문에 그냥 for문을 돌려서 찾을 경우 최악의 경우 100,000X100,000번 연산을 수행해야 하기 때문에 시간 초과가 발생

Solution

N개의 자연수를 입력 받으면서 N까지 합을 저장하는 배열을 만든다 (1부터 저장한다)
즉 accu[i]는 accu[i-1] (이전까지의 합)에 현재 숫자를 더해준 값을 저장한다
to에서부터 from까지의 구간합을 구할 때, to까지의 구간 합 즉, accu[to]에서 from이전까지의 구간합 accu[from-1]을 빼준다

Source Code

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

public class BOJ11659 {
	static int N, M;
	static int[] accu;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		accu=new int[N+1];
		st=new StringTokenizer(br.readLine());
		
		for (int i=1; i<=N; i++) {
			accu[i]=Integer.parseInt(st.nextToken())+accu[i-1];
		}
		
		//M개의 구간 합
		StringBuilder sb=new StringBuilder();
		for (int i=0; i<M; i++) {
			st=new StringTokenizer (br.readLine());
			int from=Integer.parseInt(st.nextToken());
			int to=Integer.parseInt(st.nextToken());
			
			sb.append(accu[to]-accu[from-1]).append("\n");
		}
		System.out.println(sb.toString());
	}

}

💡11660 구간합5_1

Idea

위에서 풀었던 문제와 동일하게 한 행당 누적합을 저장한다
누적합은 매 행마다 따로 적용이 되며 예를 들어 (5,5)에 저장된 값은 (5,1), (5,2), (5,3), (5,4), (5,5)에 있는 값의 합이다

Solution

위의 그림과 같이 처음 시작점을 (x1, y1)이라 하고 도착 지점을 (x2, y2)라 했을 때, 빨간 구역은 (x1, y2) + (x1+1, y2) + .... + (x2, y2) 이고 초록색 구역은 (x1, y1-1) + (x1+1, y1-1) + ..... + (x2, y1-1) 으로 계산한다

식으로 나타내면 아래와 같다

for (int x=x1; x<=x2; x++) 
    sum+=accu[x][y2]-accu[x][y1-1];

Source Code

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

public class Main {

	static int N,M;
	static int[][] accu; // <= 이전 수부터 합을 미리 계산, 행별로 각각 누적 계산
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		accu=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++) {
				accu[i][j]=accu[i][j-1]+Integer.parseInt(st.nextToken());
			}
		}
		
		StringBuilder sb=new StringBuilder ();
		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=0;
			for (int x=x1; x<=x2; x++) {
				sum+=accu[x][y2]-accu[x][y1-1];
			}
			sb.append(sum).append("\n");
		}
		System.out.println(sb.toString());
	}
}

💡11660 구간합5_2

Idea

구간합을 저장할 때, 구간 합의 범위를 다시 생각해본다
이전에는 한 행을 기준으로 부분합을 저장했다면 이번에는 아래와 같이 저장한다

Solution

아래와 같이 구하고자 하는 영역이 1번 그림과 같을 때, 주황색 영역에서 초록색 부분을 두 개 빼준다. 이 때 그림 4번에서 동그라미 친 영역은 두 번 빠지기 때문에 한 번 더해준다

시작 부분 좌표를 (x1, y1), 도착 좌표를 (x2, y2)라고 할 때, 주황색 영역=accu[x2][y2], (3)번의 초록색 영역=accu[x1-1][y2], (4)번의 초록색 영역=accu[x2][y1-1], 중복되는 영역=accu[x-1][y1-1] 이고 이를 식으로 나타내면 아래와 같다
```
accu[x2][y2]-accu[x1-1][y2]-accu[x2][y1-1]+accu[x1-1][y1-1]
```

Source Code

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

public class Main {

	static int N,M;
	static int[][] accu; // <= 이전 수부터 합을 미리 계산, 행별로 각각 누적 계산
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		accu=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++) {
				accu[i][j]=accu[i-1][j]+accu[i][j-1]-accu[i-1][j-1]+Integer.parseInt(st.nextToken());
			}
		}
		
		StringBuilder sb=new StringBuilder ();
		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=0;
			
			sb.append(accu[x2][y2]-accu[x1-1][y2]-accu[x2][y1-1]+accu[x1-1][y1-1]).append("\n");

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