Coding_Test_C++
BaekJoon 11660번: 구간 합 구하기 5(C++)
펄크럼
2021. 6. 22. 15:49
https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
풀이법
1) 단순 반복문으로는 시간 초과가 발생하기에 DP를 이용해서 푸는 문제이다.
2) 각 행의 합을 구해두고 이를 활용하는 방식으로 문제를 해결했다.
3) 좌표가 들어오는 경우 점화식을 활용하여, sum 값을 구해 주었다.
for (int i = 0; i < m; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int sum = 0;
for (int j = x1; j <= x2; j++)
{
sum += arr[j][y2] - arr[j][y1 - 1];
}
cout << sum<<"\n";
}
조건이 y2>=y1이기에, 같은 행에서 나올 수 있는 최대 값인 arr[j][y2]에서, arr[j][y1-1]을 빼주는 방식으로 문제를 해결하였다.
#include<iostream>
using namespace std;
int n,m;
int arr[1025][1025];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int temp;
cin >> temp;
arr[i][j] = arr[i][j - 1] + temp;
}
}
for (int i = 0; i < m; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int sum = 0;
for (int j = x1; j <= x2; j++)
{
sum += arr[j][y2] - arr[j][y1 - 1];
}
cout << sum<<"\n";
}
}