자료구조&알고리즘/백준

16507번: 어두운 건 무서워 [JAVA]

yong_ღ'ᴗ'ღ 2023. 8. 19. 01:13

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

 

접근 방식) 누적합

1. int[][] arr 배열 → 행 별로 누적합을 저장한다.

          밝기 정보          행별 누적합

    ex) 4 1 3 4 9 5    → 4  5  8 12 21 26

          1 2 8 7 5 5         1 3 11 18 23 28 

                   :                             :

2. 입력받은 (r1, c1) (r2, c2) 에 대해 반복문을 돌며 행별로 누적합 구한다.

    int sum = 0;

    sum += arr[r1][c2] - arr[r1][c1 - 1]; 

    r1을 r2까지 증가시키면서 더하는걸 반복해주면 → 사진 일부분의 밝기 총 합을 구할 수 있다.

 

3. 밝기 평균을 구해야 하니, 사진 일부분의 pixel 개수를 구해야 한다.

int totalPixel = 가로 개수 * 세로 개수 = (r2 - r1 + 1) * (c2 - c1 + 1);

 

→ sum(밝기 총 합) / totalPixel(pixel 개수) 를 해주면, 직사각형의 밝기 평균을 구할 수 있다.

 

package codingTestStudy.week4;

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

public class B_16507 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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[][] arr = 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++) {
                // 각 행 별로 누적합 구함
                arr[i][j] = arr[i][j - 1] + Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < Q; i++) {
            int sum = 0;
            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());

            for (int j = r1; j <= r2; j++)
                sum += arr[j][c2] - arr[j][c1 - 1];

            int totalPixel = (r2 - r1 + 1) * (c2 - c1 + 1);
            sb.append(sum / totalPixel).append('\n');
        }
        System.out.print(sb);
    }
}