16507번: 어두운 건 무서워 [JAVA]
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);
}
}