Funcia
Lv.2gridprefix-sum

직사각형 영역의 합

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 격자 grid와 질의 배열 queries가 주어집니다. 각 질의 queries[k] = [r1, c1, r2, c2]는 왼쪽 위 칸 (r1, c1)부터 오른쪽 아래 칸 (r2, c2)까지의 직사각형 영역을 뜻합니다(양 끝 포함).

각 질의 영역에 들어 있는 값의 합을 질의 순서대로 배열에 담아 반환하세요.

입출력 예

gridqueriesresult
[[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[]

제한 사항

  • 1≤H,W≤5001 \le H, W \le 500 (grid는 H×WH \times W 직사각형)
  • −106≤-10^6 \le grid[i][j] ≤106\le 10^6
  • 1≤1 \le queries.length ≤200,000\le 200{,}000
  • 0≤r1≤r2<H0 \le r1 \le r2 < H, 0≤c1≤c2<W0 \le c1 \le c2 < W
  • 합은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

시간
O(HW + Q)
공간
O(HW)

입출력 예

gridqueries기대 출력
[[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비트 정수로 만드세요.

복잡도 목표

질의마다 영역을 직접 더하는 풀이는 O(Q⋅HW)O(Q \cdot HW)라 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)296 ms추정
C++ (GCC, gnu++23)296 ms도출됨
Python 3.131000 ms도출됨
Java 251996 ms도출됨
Kotlin 2.4 (JVM)1592 ms추정
C# 14 (.NET 10)1592 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness406판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.