풀이 방법
처음에 반복문을 통해 풀이했는데 시간초과가 나왔다. 사진크기가 1000*1000이고 Q가 10000이 된다면 1000 * 1000 * 10000번 연산하게 되어 제한시간이 초과되는 것으로 보인다.
prefix sum 방법을 사용해서 풀이 했다. 배열의 (0,0) 부터 (x,y) 까지의 합을 우선 구해두고 계산할 때 꺼내 쓰는 방식이다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
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[][] array = new int[R + 1][C + 1];
for (int i = 1; i < R + 1; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < C + 1; j++) {
array[i][j] = array[i - 1][j] + array[i][j - 1] - array[i - 1][j - 1] + Integer.parseInt(st.nextToken());
}
}
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 = array[r2][c2] - array[r1 - 1][c2] - array[r2][c1 - 1] + array[r1 - 1][c1 - 1];
System.out.println(sum / ((r2 - r1 + 1) * (c2 - c1 + 1)));
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
벽 부수고 이동하고 - 2206번 (0) | 2021.10.15 |
---|---|
무기 공학 - 18430번 (0) | 2021.10.15 |
에너지 모으기 - 16198번 (0) | 2021.10.08 |
빙산 - 2573번 (0) | 2021.10.07 |
크게 만들기 - 2812번 (0) | 2021.10.07 |