[백준](C++) 11660 - 구간 합 구하기 5

BOJ 실버1 11660번입니다.
N * N 표에 숫자를 채우고 특정 범위 안의 수를 더한 합을 구하는 문제입니다.

문제

11660 구간 합 구하기 5

접근

처음에는 우선 2차원 배열에 숫자를 전부 받고, 입력받은 범위 안의 수를 전부 더해주는 식으로 풀었습니다.
이렇게 했더니 시간복잡도가 O(N^2)이 돼 시간 초과로 실패했습니다.
알고리즘 분류가 다이나믹 프로그래밍인 것에 힌트를 얻어 (1, 1)칸에서부터 (i, j)칸까지 범위의 숫자들의 합을 기억해두면 어떨까 생각해봤습니다.

위 그림에서, 회색 범위의 숫자들은 (파란 범위 + 빨간 범위 - 초록 범위) 과 같습니다.
그리고 각 범위의 숫자들의 합은 그림에 표시된 색칠된 한 칸에 저장되어 있습니다.
2차원 배열을 입력받으면서 그 수를 저장하는 게 아니라 (1, 1)부터 그 칸까지의 숫자들의 합을 저장해둡니다.

문제 풀이

• 처음 2차원 배열을 받을 때 점화식은 아래과 같이 쓸 수 있습니다.

map[i][j] = map[i][j - 1] + map[i - 1][j] - map[i - 1][j - 1] + tmp

// tmp = 해당 칸의 숫자라고 입력받은 수

• 특정 구간의 합은 아래 그림과 같이 구할 수 있습니다.
  
  위 그림에서, 우리가 원하는 검은색 범위의 숫자들은 (파랑 - 빨강 - 노랑 + 초록) 과 같습니다.
  따라서 점화식을 써보면 아래와 같습니다.

ans = map[x2][y2] - map[x1 - 1][y2] - 
	map[y1 - 1][x2] + map[x1 - 1][y1 - 1]

• 두 점화식을 이용해서 코드를 작성해줍니다.

#include <iostream>
using namespace std;

int map[1026][1026];
int n, m;
int x1, x2, y1, y2;
int tmp;

int main()
{
	ios::sync_with_stdio(0);
    	cin.tie(NULL); cout.tie(NULL);
    
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> tmp;
			map[i][j] = tmp + map[i][j - 1] + map[i - 1][j] - map[i - 1][j - 1];
		}
	while (m--)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		cout << map[x2][y2] - map[x1 - 1][y2] - map[x2][y1 - 1] + map[x1 - 1][y1 - 1] << '\n';
	}
	return 0;
}

입출력 예시

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

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

1
2
3
4