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

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

16507번: 어두운 건 무서워

1. 문제 설명

 

문제

• 호근이에게 보여줄 R*C 크기의 사진이 주어질 때, 사진의 일부분에 해당하는 밝기의 평균을 구하여라

 

2. 풀이

 

사진의 크기를 나타내는 R, C(1 <=R, C <=1,000)와 사진의 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q(1 <=Q <=10,000)이 주어진다.

 

완전 탐색으로 풀게 될 경우, Q*R*C의 경우의 수를 가지게 되고 10,000,000,000으로 시간 초과가 발생한다.

 

따라서 누적합으로 문제를 풀 수 있다.

 

(1,1)부터 (x, y)까지의 누적합을 저장하는 picture를 사용한다.

 

(1,1)부터 (x, y)까지의 누적합을 저장할 때 구간을 나누어 저장한다.

 

1. (1,1) ~ (x-1, y)까지의 누적합 -> dp [x-1][y]

2. (x,1) ~ (x, y-1)까지의 누적합 -> sum변수

 

sum 변수는 for문을 시작할 때 0으로 초기화하여 더해나간다.

 

r1, c1, r2, c2 구간합은 picture 변수를 이용해 구할 수 있다.

 

picture [r2][c2] = (1,1) ~ (r2, c2)까지의 누적합

 

picture [r2][c2]에서 우리가 원하지 않는 구간 (1,1) ~ (r1-1, c2), (1,1) ~ (r2, c1-1)의 구간 정보를 빼주면 된다.

 

이때, (1,1)~ (r1-1, c1-1) 구간이 2번 빼 지게 되므로 이 구간을 한번 더해주면 된다.

 

이것을 수행하면 아래와 같다.

 

picture [r2][c2]-picture [r1-1][c2]-picture [r2][c1-1]+picture [r1-1][c1-1] = (r1, c1) ~ (r2, c2)까지의 누적합

 

평균을 구하는 문제이므로 누적합을 (r1, c1), (r2, c2) 크기에 해당하는 직사각형의 크기로 나누어주면 된다.

 

 

*로직

1. 누적합 (picture)을 구한다.

2. (r1, c1), (r2, c2)의 구간합을 구한다.

3. 구간합을 직사각형의 크기로 나누어 평균을 출력한다.

 

3. 코드

// JAVA 11 , 메모리 : 80120KB, 시간 : 592ms

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int width, height, question, sum;
        int r1, c1, r2, c2;
        
        //(1,1) ~ (x,y)까지의 합 저장
        int[][] picture;

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

        width = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());
        question = Integer.parseInt(st.nextToken());

        picture = new int[width + 1][height + 1];

        for (int x = 1; x <= width; x++) {

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

            // picture[x]의 합 저장
            sum = 0;

            for (int y = 1; y <= height; y++) {

                sum += Integer.parseInt(st.nextToken());
                picture[x][y] = sum + picture[x - 1][y];
            }
        }

        for (int x = 0; x < question; x++) {
            st = new StringTokenizer(br.readLine());

            r1 = Integer.parseInt(st.nextToken());
            c1 = Integer.parseInt(st.nextToken());
            r2 = Integer.parseInt(st.nextToken());
            c2 = Integer.parseInt(st.nextToken());

            sb.append((picture[r2][c2] - picture[r1 - 1][c2] - picture[r2][c1 - 1] + picture[r1 - 1][c1 - 1]) / ((r2 - r1 + 1) * (c2 - c1 + 1))).append("\n");

        }

        System.out.print(sb);

    }

}