https://www.acmicpc.net/problem/11660
문제
> N×N개의 수가 N×N 크기의 표에 채워져 있다.
> (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오.
> (x, y)는 x행 y열을 의미한다.
> 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
> 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
> 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.접근
누적합을 사용한다. NxN의 표를 입력받으면서 동시에 해당 좌표까지의 누적합을 계산해서 벡터에 저장한다.
예를들어 2,2는 (2,1까지의 합) + (1,2까지의 합) + 2,2좌표 - 1,1이다. 1,1은 2,1과 1,2에서 겹쳐 두번 더했기 때문에 빼준다.
N이 1부터시작하므로 벡터의 크기를 N+1로 주고 0번인덱스에 대해 각각 전부 0으로 초기화해준다. 그러면 sum(1,1), 1,0등등 에대해서도 0의 좌표들을 이용해 위 수식으로 구할 수 있다.
sum을 다 구했으면 M에 대해 구간합을 구해야한다.
예제를 통해 식을 구해보면 2,2부터 3,4는 sum(3,4)에서 sum(1,4)를 빼고, sum(3,2)를 빼주고 둘의 겹치는 부분인 sum(1,2)를 더해주면 된다.
3,4부터 3,4는 sum(3,4)에서 sum(3,3), sum(2,4)를 뺴주고 sum(2,3)을 더해주면 된다.
이 둘을 통해 규칙을 구해보면 최대 구간에서 행을 최대구간, 열을 최소구간-1로 갖는 합과 행을 최소구간-1, 열을 최대구간으로 가지는 합을 빼준뒤 둘의 겹치는 부분인 최소구간의 행-1, 최소구간의 열-1 까지의 합을 더해주는것이다.
문제해결
> 행렬의 크기와 구할 구간의 수를 입력받는다.
> 행렬의 크기와 행렬을 통해 구할 누적합 벡터를 선언한다.
> 행렬을 입력받으면서 동시에 sum을 구한다.
구하려는 좌표의 행-1, 열까지의 합과, 행, 열-1까지의 합을 더하고 해당 좌표를 더한뒤 겹치는 행-1,열-1의 합을 빼주면 된다.
> M번의 구간에 대해 구한다.
> 최대구간의 합에서 최소구간-1행, 최대구간열까지의 합과, 최대구간의 행, 최소구간-1열 까지의합을 빼준뒤 중복으로 빼준 최소구간-1행 최소구간-1열까지의 합을 더해준다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<int>> num(N + 1, vector<int>(N + 1, 0));
vector<vector<int>> sum(N + 1, vector<int>(N + 1, 0));
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> num[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + num[i][j] - sum[i - 1][j - 1];
}
}
while (M--)
{
int i, j, t, k;
cin >> i >> j >> t >> k;
cout << sum[t][k] - sum[i - 1][k] - sum[t][j - 1] + sum[i - 1][j - 1] << '\n';
}
}
후기
전에 몇번 누적합, 구간합문제를 풀어봐서 접근이 어렵진 않았지만 합을 구하는법과 구간의 합을 구하는 법이 가물가물해서 다시 규칙을 찾아내봤다. 다시 머릿속에 기억됐다.
