알고리즘/누적합 & 구간합
백준 11660번: 구간 합 구하기 5 [구간합][누적합][DP] -Java
또또쪼
2023. 8. 7. 17:20
728x90
300x250
https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
[구간 합 구하기 3]에서 더 업그레이드 된 문제. 2차원 배열이 되었다..!!
<첫 번째 시도 - 시간초과>
행별로 누적합을 구한다음 그 행만큼 for문 돌려서 범위지정하여 최종합을 구하는 방식이다.
O(N*M)인데 시간초과 났다. 100,000 * 1024 하면 딱 1억번정돈데.. 걸렸넹 ㅠㅋ
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
//System.setIn(new FileInputStream("Test.txt"));
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++) {
int num = Integer.parseInt(st.nextToken());
sum[i][j] = sum[i][j-1]+num;
}
}
// for (int i = 0; i < sum.length; i++) {
// for (int j = 0; j < sum.length; j++) {
// System.out.print(sum[i][j]+ " ");
// }
// System.out.println();
// }
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int sx = Integer.parseInt(st.nextToken());
int sy = Integer.parseInt(st.nextToken());
int ex = Integer.parseInt(st.nextToken());
int ey = Integer.parseInt(st.nextToken());
int result = 0;
for (int i = sx; i <= ex; i++) {
result += sum[i][ey] - sum[i][sy-1];
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(result+"\n");
bw.flush();
}
}
}
<두 번째 시도 - 맞았습니다!>
패드로 끄적인 내용을 복붙..
728x90
요는
1. 2차원배열 누적합 구하기
2. 누적합배열을 이용하여 값 도출하기
1의 누적합배열 구하는 방법은 1.1부터 특정 지점까지 네모를 그린다치고 거기에 포함된 모든 값을 다 더하는 경우이다.
for문을 또 돌지 않아도 되기때문에 O(M) = O(1)로 끝난다.
728x90
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
//System.setIn(new FileInputStream("Test.txt"));
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 map[][] = new int[N+1][N+1];
int sum[][] = new int[N+1][N+1]; //1부터 네모범위 구간합
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <=N; j++) {
int num = Integer.parseInt(st.nextToken());
map[i][j] = num;
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+num;
}
}
// for (int i = 0; i < sum.length; i++) {
// for (int j = 0; j < sum.length; j++) {
// System.out.print(sum[i][j]+ "\t");
// }
// System.out.println();
// }
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int sx = Integer.parseInt(st.nextToken());
int sy = Integer.parseInt(st.nextToken());
int ex = Integer.parseInt(st.nextToken());
int ey = Integer.parseInt(st.nextToken());
int result = 0;
// //행 구간합일 경우 행만큼 돌아서 sum
// for (int i = sx; i <= ex; i++) {
// result += sum[i][ey] - sum[i][sy-1];
// }
result = sum[ex][ey] - sum[sx-1][ey]-sum[ex][sy-1]+sum[sx-1][sy-1];
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(result+"\n");
bw.flush();
}
}
}728x90