[Java] 백준 11660.구간 합 구하기 5

➡️문제 링크

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

 

 

💡아이디어

누적합

처음에는 M개의 좌표를 입력받을 때마다 하나하나 계산하려고 했는데

매번 계산하는 것보다는 값을 미리 구해서 그때그때마다 그 값만 가져와서 쓰면 되지 않을까라는 생각이 들며

누적합으로 접근해야 겠다고 생각했다. 

처음에는 이렇게 더하는 줄 알고, 

행을 기준으로  for문을 돌며

i == x1, i == x2, 그 외의 경우를 나누어 구했는데 틀렸다

그래서 다시 읽어보니, 시작점은 y1, 끝점은 y2로 해서 구해야했다

 

 

✏️문제 풀이

1. 누적 합  -   성공

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

public class Main {
	static int N, M;
	static int [][] map;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = 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++) {
				map[i][j] = Integer.parseInt(st.nextToken()) + map[i][j-1];	// 누적합
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int t = 0; t < M; t++) {
			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 i = x1; i <= x2; i++) {
				sum += map[i][y2] - map[i][y1 - 1];			
			}
			
			sb.append(sum+"\n");
		}
		
		// 정답 출력
		System.out.println(sb);

	}

}

 

 

2. 누적 합,  DP  - 성공

생각보다 시간복잡도가 커서 다른 사람들이 문제 풀이를 보니

누적합 + DP로 접근했다

 

예를들어, a[2][2]를 구해야 한다고 가정해보자 (a[i][j]는 (1, 1) ~ (i, j)까지의 합, 즉 직사각형 구하기)

1 + 2 + 3 + 4 = 10

이렇게 정답이 나온다는 것을 확인할 수 있다.

 

이제 쪼개서 구해보자

1. 위쪽 영역 -> a[1][2] : 1 + 2
2. 왼쪽 영역 -> a[1][2] : 1 + 3
3. 자기자신 -> map[2][2] : 4 

여기서 공통적으로 겹치는 부분이 존재한다.

바로 1, a[i-1][j-1]

그럼 이 부분을 마지막으로 한 번 더 빼주면, 구하고자 하는 값이 나온다.

a[i][j] = a[i-1][j] + a[i][j-1] + map[i][j] - a[i-1][j-1]

 

 

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

public class Main {
	static int N, M;
	static int [][] map;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = 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++) {
				int tmp = Integer.parseInt(st.nextToken());
				map[i][j] =  tmp + map[i-1][j] + map[i][j-1] - map[i-1][j-1];	// (1, 1) - (i, j)까지의 사각형 합
				}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int t = 0; t < M; t++) {
			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 = map[x2][y2] - map[x2][y1-1] - map[x1-1][y2] + map[x1-1][y1-1];	
			
			sb.append(sum+"\n");
		}
		
		// 정답 출력
		System.out.println(sb);

	}

}