Lv.2gridprefix-sum
직사각형 영역의 합
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
정수 격자 grid와 질의 배열 queries가 주어집니다. 각 질의 queries[k] = [r1, c1, r2, c2]는
왼쪽 위 칸 (r1, c1)부터 오른쪽 아래 칸 (r2, c2)까지의 직사각형 영역을 뜻합니다(양 끝 포함).
각 질의 영역에 들어 있는 값의 합을 질의 순서대로 배열에 담아 반환하세요.
입출력 예
| grid | queries | result |
|---|---|---|
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] | [[0, 0, 1, 1], [1, 1, 2, 2], [0, 0, 2, 2], [2, 0, 2, 0]] | [12, 28, 45, 7] |
[[-3, 5]] | [[0, 1, 0, 1], [0, 0, 0, 1]] | [5, 2] |
입출력 예 설명
예 1 — [0, 0, 1, 1]은 1 + 2 + 4 + 5 = 12, [1, 1, 2, 2]는 5 + 6 + 8 + 9 = 28입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(grid: int[][], queries: int[][]) → long[]
제한 사항
- (
grid는 직사각형) -
grid[i][j] -
queries.length - ,
- 합은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(HW + Q)
- 공간
- O(HW)
입출력 예
| grid | queries | 기대 출력 |
|---|---|---|
[[1,2,3],[4,5,6],[7,8,9]] | [[0,0,1,1],[1,1,2,2],[0,0,2,2],[2,0,2,0]] | [12,28,45,7] |
[[-3,5]] | [[0,1,0,1],[0,0,0,1]] | [5,2] |
힌트
힌트
1차원 누적 합을 2차원으로 넓히면 됩니다.
S[i][j] = 왼쪽 위 (0, 0)부터 (i-1, j-1)까지의 합 (크기 (H+1) × (W+1), 0행·0열은 0)
S[i][j] = grid[i-1][j-1] + S[i-1][j] + S[i][j-1] - S[i-1][j-1] — 위쪽과 왼쪽을 더하면 겹친 부분이 두 번 들어가니 한 번 뺍니다.
질의는 같은 원리로 네 값을 조합합니다.
sum = S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]
누적 합은 64비트 정수로 만드세요.
복잡도 목표
질의마다 영역을 직접 더하는 풀이는 라 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 296 ms | 추정 |
| C++ (GCC, gnu++23) | 296 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1996 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1592 ms | 추정 |
| C# 14 (.NET 10) | 1592 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 6 | 판정만 |
| performance | 60 | 4 | 판정만 |