합 배열 S를 만드는 공식
S[i] = S[i-j] + A[i]
i에서 j까지 구간 합
S[j] - S[i-1]
이차원 배열일 때 D[i][j] 합 공식
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]
반응형
'개발로그 > 알고리즘' 카테고리의 다른 글
| 프로그래머스 Lv.0 다항식 더하기 (0) | 2023.07.30 |
|---|---|
| 프로그래머스 Lv.0 문자열 여러 번 뒤집기 (0) | 2023.07.30 |
| 프로그래머스 Lv.0 옹알이(1) (0) | 2023.07.30 |
| 프로그래머스 Lv.0 삼각형의 완성조건 (0) | 2023.07.30 |
| 프로그래머스 Lv.0 직사각형 넓이 구하기 (0) | 2023.07.30 |
댓글