https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
구간 합 구하기 4에서 사용했던 수열의 부분합 공식 Ai + A(i+1) + ... + Aj = Sj - S(i-1)을 떠올려보자. 이 공식을 2차원으로 확장할 수 있다면 해결할 수 있는 문제다.
다음 그림을 보자.
계산할 구간이 입력으로 3, 3, 4, 4가 들어왔다. 위의 색칠한 부분이 이에 해당한다. 이 부분을, 맨 왼쪽 위의 점을 하나의 꼭지점으로 갖는 직사각형을 통해 나타낼 수 있을까? 예를 들면....
짜잔. (4)는 (2)와 (3)에서 겹치는 부분으로, 두 번 뺄셈되었으므로 다시 한 번 더해줬다.
그래서 이 직사각형들을 어디에 써먹는가? 여기까지 떠올리면 바로 문제를 풀러가면 된다.
입력받은 표와 동일한 크기의 2차원 배열 sum을 생성해보자. 그리고 sum[i][j]의 값을 맨 왼쪽 위 점(1,1)에서 시작해 점 (i,j)에서 끝나는 직사각형에 포함되는 원소들의 합이라고 해보자. 위의 예시를 sum[i][j]로 나타내면 다음과 같다.
문제 해결의 실마리가 모두 주어졌다..... 남은 것은 동적 계획법을 이용해 sum 배열의 값을 채우는 것 뿐이다.
주요 코드
더보기
int main(){
//setup
for (int i = 1; i <= size; i++) {
sum[1][i] = sum[1][i - 1] + v[1][i];
sum[i][1] = sum[i - 1][1] + v[i][1];
}
//fill
for (int i = 1; i <= size; i++)
for (int j = 1; j <= size; j++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + v[i][j];
}
int getIntervalSum(Matrix& sum, int x1, int y1, int x2, int y2) {
return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
'백준' 카테고리의 다른 글
백준 17298 - 오큰수 (0) | 2023.08.02 |
---|---|
백준 2206 - 벽 부수고 이동하기 (미해결, 틀린 원인) (0) | 2023.07.26 |
백준 1865 - 웜홀 (WA, 오답 원인) (0) | 2023.07.25 |
백준 N과 M (2), (5), (9) (0) | 2023.07.25 |
백준 11404 - 플로이드 (0) | 2023.07.25 |