[BOJ] 11660번 구간 합 구하기 5

시간 초과 난 코드

import java.util.Scanner;
//
public class Main_11660_ {

	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		int n = sc.nextInt();//크기
		int m = sc.nextInt();//m개의 횟수
		//열별로 누적합 구함
		int[][] cumulatedSumArr = new int[n+1][n+1];
		for(int i = 1 ; i <=n; i++ ) {
			int tmp = 0;
			for(int j =1; j<=n; j++) {
				tmp = sc.nextInt();
				cumulatedSumArr[i][j] =cumulatedSumArr[i][j-1] + tmp;
			}
		}

		
		for(int k = 0; k < m; k++) {
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			int x2 = sc.nextInt();
			int y2 = sc.nextInt();
			int ans = 0;
			
			for(int i = 0; i <= x2 - x1; i++) { //0~3
				ans += cumulatedSumArr[x1+i][y2] - cumulatedSumArr[x1+i][y1-1];
			}
			
			System.out.println(ans);
		}
	}

}

첫번째 풀이 코드

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

public class Main_11660_xxx {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] sigma = 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++) { // 2차원 누적 시그마 배열 만들기
				//해당 위치의 원소까지의 누적합 = 왼쪽원소의 누적합 + 위쪽 원소의 누적합 - 대각선 누적합 
				sigma[i][j] = sigma[i-1][j]+sigma[i][j-1]-sigma[i-1][j-1]+Integer.parseInt(st.nextToken());
			}
		}
		
		StringBuilder sb= new StringBuilder();
		for(int m=0; m<M; m++) {
			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;
			sum = sigma[x2][y2]-sigma[x1-1][y2]-sigma[x2][y1-1]+sigma[x1-1][y1-1];
//			System.out.println(sum); // M의 범위가 10만이라 출력이 너무 많아서 시간터짐.
			sb.append(sum+"\n");
		}
		System.out.println(sb);
	}
}

두번째 풀이 코드

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

public class Main_11660_xxx {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] sigma = 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++) { // 2차원 누적 시그마 배열 만들기
				//해당 위치의 원소까지의 누적합 = 왼쪽원소의 누적합 + 위쪽 원소의 누적합 - 대각선 누적합 (두 번 중복됐으니까 뻼) + 현재 위치 원소값
				sigma[i][j] = sigma[i-1][j]+sigma[i][j-1]-sigma[i-1][j-1]+Integer.parseInt(st.nextToken());
			}
		}
		
		StringBuilder sb= new StringBuilder();
		for(int m=0; m<M; m++) {
			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;
			sum = sigma[x2][y2]-sigma[x1-1][y2]-sigma[x2][y1-1]+sigma[x1-1][y1-1];
            			//마지막 더하기는 추가되는 겹쳐서 두 번 빠지기 떄문에 한번 더해준다. 
//			System.out.println(sum); // M의 범위가 10만이라 출력이 너무 많아서 시간터짐.
			sb.append(sum+"\n");
		}
		System.out.println(sb);
	}
}

풀이

• 앞선 4번 문제와 같이 누적합으로 풀기 위해서 이차원배열을 열 기준 누적합으로 만들어서 풀었지만 시간 초과가 났다.
• 첫번째 풀이 코드를 보면 열 기준 누적합으로 푼 것은 같지만 BufferedReader로 입력 받고 StringBuffer로 출력했을 때 아슬아슬하게 통과가 된다.
• ⭐⭐ 두번째 풀이 코드를 보면 해당 위치의 원소까지의 누적합 = 왼쪽원소의 누적합 + 위쪽 원소의 누적합 - 대각선 누적합 (두 번 중복됐으니까 뻼) + 현재 위치 원소값 누적합 이차원 배열을 채운다. 따라서 이차원 배열의 원소는 1,1부터 해당 위치까지의 누적합을 의미한다.

sum = sigma[x2][y2]-sigma[x1-1][y2]-sigma[x2][y1-1]+sigma[x1-1][y1-1];
//마지막 더하기는 추가되는 겹쳐서 두 번 빠지기 떄문에 한번 더해준다. 

그래서 최종적인 값은 누적합 원소에서 포함되지 않는 그 시작위치 전의 범위들을 빼준다. 그리고 마지막 더하기는 추가되는 겹쳐서 두 번 빠지기 떄문에 한번 더해준다.