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

 

16507번: 어두운 건 무서워

첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사

www.acmicpc.net

코드설명

누적합을 사용할경우,

처음에 누적합 배열을 구하는데에는 O(N*N)의 시간복잡도가 주어지지만, 합을 구하는 연산이 O(1)로 줄어듭니다.

 

1. 누적합배열을 구하기

for(int i=1;i<=N;i++) {
    for(int j=1;j<=M;j++) {
        prefixSum[i][j] = arr[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
    }
}
  • prefixSum[i][j] = 배열값 + 왼쪽 누적합 + 위쪽 누적합 - 교집합 누적합

 

2. 구간합 구하기

int result = prefixSum[x][y] - prefixSum[x][j-1] - prefixSum[i-1][y] + prefixSum[i-1][j-1];
  • 합연산 = 전체 누적합 - 왼쪽 누적합 - 위쪽 누적합 + 교집합 누적합

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int R, C, Q;
	public static int[][] arr;
	public static int[][] prefixSum;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
 
    	R = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	Q = Integer.parseInt(st.nextToken());
    	
    	prefixSum = new int[R+1][C+1];
    	arr = new int[R][C];
    	
    	for(int i=0;i<R;i++) {
    		st = new StringTokenizer(br.readLine());	
    		for(int j=0;j<C;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=1;i<=R;i++) {
    		for(int j=1;j<=C;j++) {
    			prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] + arr[i-1][j-1] - prefixSum[i-1][j-1];
    		}
    	}
    	
    	
    	for(int i=0;i<Q;i++) {
        	st = new StringTokenizer(br.readLine());
        	int r1 = Integer.parseInt(st.nextToken());
        	int c1 = Integer.parseInt(st.nextToken());
        	int r2 = Integer.parseInt(st.nextToken());
        	int c2 = Integer.parseInt(st.nextToken());
        	
        	int value = prefixSum[r2][c2] - prefixSum[r2][c1-1] - prefixSum[r1-1][c2] +prefixSum[r1-1][c1-1];
        	int answer = value / ((r2 - r1 + 1) * (c2 - c1 + 1));
        	System.out.println(answer);    		
    	}
 
    	
    }
}

'알고리즘 > Prefix_Sum' 카테고리의 다른 글

[백준] 2559 수열 - 누적합(Prefix Sum) + 슬라이딩 윈도우(Sliding Window) JAVA  (0) 2023.11.22
[백준] 2851 슈퍼 마리오 - 누적합(Prefix Sum) JAVA  (0) 2023.11.22
[백준] 11441 인간-컴퓨터 상호작용 - 누적합(Prefix Sum) + DP + 알파벳(문자열) JAVA  (0) 2023.08.13
[백준] 11441 합 구하기 - 누적합(Prefix Sum) JAVA  (0) 2023.08.13
[백준] 11659 구간 합 구하기 4 - 누적합(Prefix Sum) JAVA  (0) 2023.08.13

+ Recent posts

티스토리툴바