백준 11660 구간 합 구하기5
by 진혀크
문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
예제
예제 입력
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4
예제 출력
27
6
64
나의 접근 방법
구간 합을 미리 구해놓은 후 빼줘야 할 값들을 빼주고 중복되는 값을 더해주는 방식(Prefix Sum 활용)
예제의 입력 값인 2 2 3 4를 기준으로 생각해보자.
우리가 구하고 싶은 값은 (1,1)에서 (3,4)까지의 합을 구한 값에서 (1,1)에서 (1,4)까지의 합과 (1,1)에서 (3,1)까지의 합을 뺀 후 (1,1)에서 (1,1)까지의 합을 더한 값과 같다.
그림으로 보면 다음과 같다.
누적 합을 구해놓은 배열을 기준으로 보면 빨간 칸들의 값을 더한 값에서 파란 칸들의 값을 뺀 값이 정답이 된다.
코드
#include<iostream>
#include<vector>
using namespace std;
int main(void){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin>>N>>M;
vector<vector<int>> arr(N+1, vector<int>(N+1, 0)), dp(N+1, vector<int>(N+1, 0));
for(int i = 1 ; i<=N ; i++){
for(int j = 1 ; j<=N ; j++){
cin>>arr[i][j];
}
}
for(int i = 1 ; i<=N ; i++){
for(int j = 1 ; j<=N ; j++){
dp[j][i] = dp[j-1][i] + arr[j][i];
}
}
for(int i = 1 ; i<=N ; i++){
for(int j = 1 ; j<=N ; j++){
dp[i][j] = dp[i][j] + dp[i][j-1];
}
}
for(int i = 0 ; i<M ; i++){
int x1, x2, y1, y2;
cin>>x1>>y1>>x2>>y2;
cout<<dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1]<<'\n';
}
return 0;
}
특이사항
input과 output이 많기 때문에 입출력 속도를 빠르게 해주지 않으면 시간 초과가 난다. 주의하자!
Subscribe via RSS