728x90
반응형
🟥 2차원 구간 합 배열 D[X][Y] 정의
D[X][Y] = 원본 배열의 (0,0) 부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합
⚛️ D[X][Y]의 값을 채우는 구간 합 공식
D[ i ][ j ] = D[ i ][ j - 1 ] + D[ i - 1][ j ] - D[ i - 1 ][ j - 1] + A[ i ][ j ]
❗질의 X1, Y1, X2, Y2에 대한 답을 합으로 구하는 방법
D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1 - 1][Y1 - 1]
관련 문제
https://www.acmicpc.net/problem/11660
반응형
'Knowledge > 알고리즘' 카테고리의 다른 글
| 깊이 우선 탐색 (DFS : Depth-First Search) (0) | 2024.06.23 |
|---|---|
| 정렬 알고리즘 정의 요약 (0) | 2024.06.18 |
| 에라토스테네스의 체 (0) | 2024.06.11 |
| [알고리즘] 백트래킹 (Backtracking) (1) | 2023.12.06 |
| [알고리즘] 그리디 알고리즘 (Greedy Algorithm) (4) | 2023.12.05 |