[백준](C++) 11660 - 구간 합 구하기 5
BOJ 실버1 11660번입니다.
N * N 표에 숫자를 채우고 특정 범위 안의 수를 더한 합을 구하는 문제입니다.
문제
접근
처음에는 우선 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
Author And Source
이 문제에 관하여([백준](C++) 11660 - 구간 합 구하기 5), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@venniek/백준C-11660-구간-합-구하기-5저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)