[알고리즘] 백준 > #16507. 어두운 건 무서워

문제링크

백준 #16507. 어두운 건 무서워

풀이방법

매번 구간합, 평균을 구하면 당연히 시간초과가 뜨겠죠? 그래서 구간합 배열을 사용했습니다! sumTable[r][c] 값의 의미는 sumTable[1][1] 부터 sumTable[r][c] 까지 밝기의 합입니다. 이 구간합 배열을 이용해 구간 평균 밝기를 원타임에 구할 수 있습니다~ 쉬운 문제네요!

int area = sumTable[r2][c2] - (sumTable[r1 - 1][c2] + sumTable[r2][c1 - 1] - sumTable[r1 - 1][c1 - 1]);
area /= ((r2 - r1 + 1) * (c2 - c1 + 1));

코드

import java.util.*;
public class BOJ16507 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int r = sc.nextInt();
        int c = sc.nextInt();
        int q = sc.nextInt();

        int[][] sumTable = new int[r + 1][c + 1];
        for (int i = 0; i <= c; i++) sumTable[0][i] = 0;
        for (int i = 1; i <= r; i++) sumTable[i][0] = 0;

        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                sumTable[i][j] = sumTable[i][j - 1] + sumTable[i - 1][j] + sc.nextInt() - sumTable[i - 1][j - 1];
            }
        }

        StringBuilder result = new StringBuilder();
        while ((--q) >= 0) {
            int r1 = sc.nextInt();
            int c1 = sc.nextInt();
            int r2 = sc.nextInt();
            int c2 = sc.nextInt();

            int area = sumTable[r2][c2] - (sumTable[r1 - 1][c2] + sumTable[r2][c1 - 1] - sumTable[r1 - 1][c1 - 1]);
            area /= ((r2 - r1 + 1) * (c2 - c1 + 1));
            result.append(area);
            result.append("\n");
        }

        System.out.print(result.toString());
    }
}