반응형
문제링크:https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 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)
www.acmicpc.net
dp적인 생각이 있어야 하는 문제였습니다.
(1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 의 범위이므로 시간복잡도가 O(n*m)이 되면 오답입니다. ( 1억번이상 반복하기 때문에)
즉, O(m)인 방법을 생각해야합니다.
해당 그림을 보면이해하기 쉽습니다. 초록색을 구하기 위해 전체 (초록 + 보라 + 파란 + 빨강) - 보라 - 파란 - 빨강입니다. 저는 각각의 좌표에 이전부터 해당좌표까지의 값을 더해 놓았습니다.
dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y11 - 1] + dp[x1 - 1][y11 - 1] 식으로 풀 수 있었습니다.
정답코드입니다.
#include <iostream>
using namespace std;
int n = 0, m = 0;
int dp[1025][1025] = { 0 };
int num = 0, x1 = 0, y11 = 0, x2 = 0, y2 = 0;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> num;
dp[i][j] = num + dp[i][j - 1] ; // 이전행들을 중복해서 더해놓는것 1111 -> 1 2 3 4 이렇게 쌓이겠지
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] += dp[i - 1][j];
while (m--) {
cin >> x1 >> y11 >> x2 >> y2;
cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y11 - 1] + dp[x1 - 1][y11 - 1] << '\n';
}
}반응형