배열을 이중배열을 이용해서 가로길이만큼 저장을 한다 후에 한줄씩 값을 출력 하고 그 값들을 더한다.
알고리즘은 위와 같다.
처음에는 시간초과가 나왔다.
아무리 봐도 복잡도에서는 시간초과가 나올 이유가 없기에 설마 싶어서 원래는 system.out.println(x)를 사용하여 바로 출력하였지만 출력을 stringbuilder로 바꾸었다.
그랬더니 해결이 되었다.
설마설마 했는데 출력으로 시간초과가 나올줄은 몰랐다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int sum[][] = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
sum[i][j] = sum[i][j-1]+Integer.parseInt(st.nextToken());
}
}
int x[] = new int[2];
int y[] = new int[2];
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
x[0] = Integer.parseInt(st.nextToken());
y[0] = Integer.parseInt(st.nextToken());
x[1] = Integer.parseInt(st.nextToken());
y[1] = Integer.parseInt(st.nextToken());
int answer=0;
for (int j = x[0]; j <=x[1] ; j++) {
answer+=sum[j][y[1]]-sum[j][y[0]-1];
}
stringBuilder.append(answer).append("\n");
}
System.out.println(stringBuilder);
}
}