[백준/16507] 어두운 건 무서워 - JAVA

이지환·2023년 12월 18일

백준 알고리즘

알고리즘(백준) 💻

목록 보기

4/80

📌 문제

알고리즘 분류 : 누적합
난이도 : 실버1
출처 : 백준 - 유니의 편지쓰기

🦧 문제 풀이 접근

2차원 배열에 각 (0,0)부터 각 좌표까지의 합을 누적.
누적된 값의 차를 통해 (r1,c1)와 (r2,c2) 범위의 값 계산.

(r2,c2) - (r1-1,c2) - (r2,c1-1) + (r1-1,c1-1)

💻 code

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        int[][] picture = new int[R+1][C+1];
        for(int i=1;i<=R;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1;j<=C;j++) {
                picture[i][j] = Integer.parseInt(st.nextToken())+picture[i][j-1]+picture[i-1][j]-picture[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 sum = picture[r2][c2]-picture[r1-1][c2]-picture[r2][c1-1]+picture[r1-1][c1-1];
            int quality = sum/((r2-r1+1)*(c2-c1+1));
            sb.append(quality).append("\n");
        }
        System.out.println(sb);

    }
}