개발자공부일기
11660번 - 구간 합 구하기 5(C++) 본문
https://www.acmicpc.net/problem/11660
저번에 했던 구간합 문제의 2차원배열 버전이다.
이 문제도 시간이 촉박해서 구간합공식을 이용하는 문제다.
저번에 배운 cin,cout 최적화와 endl대신 개행문자를 사용했다.
#include <iostream>
#include <vector>
using namespace std;
//구간 합 문제
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int size, quiz;
cin >> size >> quiz;
//2차원 배열의 원본A, 구간합B를 0으로 초기화하여 사이즈보다 하나 크게 생성
//=> 구간합 공식을 위해 0으로 채워진 공간이 필요함
vector<vector<int>> A(size+1, vector<int>(size+1,0));
vector<vector<int>> B(size+1, vector<int>(size+1,0));
//원본배열 받으면서 구간합배열 생성
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
cin >> A[i][j];
//구간합을 구하려는 위치 기준 위에거,왼쪽거 더하고 왼쪽대각선에 있는거 빼고
//원본배열의 현위치값 더하기
B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + A[i][j];
}
}
for (int i = 0; i < quiz; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
//x1,y1 ~ x2,y2사이의 구간합 구하는 공식
int result = B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1];
cout << result << "\n";
}
return 0;
}
그래서 저 공식이 어떻게 나오는건지 알아보자
우리는 다음과 같은 2차원 배열을 입력받을 예정이다.(회색배경은 좌표를 표현하는 숫자다)
1 | 2 | 3 | 4 | |
1 | 1 | 2 | 3 | 4 |
2 | 2 | 3 | 4 | 5 |
3 | 3 | 4 | 5 | 6 |
4 | 4 | 5 | 6 | 7 |
이 배열로 합배열을 만들면
1 | 2 | 3 | 4 | |
1 | 1 | 3 | 6 | 10 |
2 | 3 | |||
3 | 6 | |||
4 | 10 |
이런식으로 1행 1열이 채워진다.
원본배열 A와 합배열 B가 있다고 했을때
행 구간합 공식:B[i][j] = B[1][j-1] + A[1][j]
열 구간합 공식:B[i][j] = B[i-1][1] + A[i][1]
2,2부터는 위에 코드처럼
구간합을 구하려는 위치 기준 위에거,왼쪽거 더하고 왼쪽대각선에 있는거 빼고 원본배열의 현위치값 더하기
공식:B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + A[i][j];
이때 i-1같은 공식의 연산을 위해 크기가 하나씩 더 큰 벡터를 생성해뒀다.
그 하나 더 큰 공간에는 0이 있어서 계산에 영향을 주지 않는다.
0 | 0 | 0 | 0 | 0 |
0 | 1 | 3 | 6 | 10 |
0 | 3 | |||
0 | 6 | |||
0 | 10 |
이런 느낌인것.
저 공식으로 모두 채우면
0 | 0 | 0 | 0 | 0 |
0 | 1 | 3 | 6 | 10 |
0 | 3 | 8 | 15 | 24 |
0 | 6 | 15 | 27 | 42 |
0 | 10 | 24 | 42 | 64 |
라는 벡터 B가 만들어진다.
이제 구간합을 구해볼건데.
일단 공식은 B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1] 이다.
왜 그렇게 나오는지 살펴보자
예를들어 2,2~3,4라고 생각해보자
0 | 0 | 0 | 0 | 0 |
0 | 1 | 3 | 6 | 10 |
0 | 3 | 8 | 15 | 24 |
0 | 6 | 15 | 27 | 42 |
0 | 10 | 24 | 42 | 64 |
저 파란 범위의 구간합을 구하려면
(1,1)부터 (3,4)의 구간합에서
0 | 0 | 0 | 0 | 0 |
0 | 1 | 3 | 6 | 10 |
0 | 3 | 8 | 15 | 24 |
0 | 6 | 15 | 27 | 42 |
0 | 10 | 24 | 42 | 64 |
0 | 0 | 0 | 0 | 0 |
0 | 1 | 3 | 6 | 10 |
0 | 3 | 8 | 15 | 24 |
0 | 6 | 15 | 27 | 42 |
0 | 10 | 24 | 42 | 64 |
두개의 노란 범위를 빼고
중복으로 뺀 1,1을 다시 더해줘야 한다.
(2,2)와 (3,4)를
B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1] 에 대입해 보면
B[3][4] - B[2 - 1][4] - B[3][2 - 1] + B[2 - 1][2 - 1] => B[3][4] - B[1][4] - B[3][1] + B[1][1] = 27 이다.
'코딩테스트 > 백준' 카테고리의 다른 글
11003번 - 최솟값 찾기(c++) (0) | 2025.07.25 |
---|---|
10986번 - 나머지 합 구하기 5(C++) (0) | 2025.06.04 |
11659번 - 구간 합 구하기 4(C++) (0) | 2025.04.30 |