BOJ
<11660번> 구간 합 구하기 5
LGTM:)
2021. 12. 12. 20:59
728x90
https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
#include<iostream>
using namespace std;
int map[1025][1025];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,times;
cin>>n>>times;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin>>map[i][j];
for (int i = 1; i <= n; i++)
{
map[i][1]+=map[i-1][1];
map[1][i]+=map[1][i-1];
}
for (int i = 2; i <= n; i++)
for (int j = 2; j <= n; j++)
map[i][j]+= map[i][j-1]+map[i-1][j]-map[i-1][j-1];
while(times--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<map[x2][y2]-map[x2][y1-1]-map[x1-1][y2]+map[x1-1][y1-1]<<'\n';
}
return 0;
}
이 문제를 풀 때, 다이나믹 프로그래밍을 사용했고, 머리로만 풀지 않고 쓰면서 식을 구했다.
728x90