합이 가장 큰 직사각형 영역
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
R행 C열의 땅이 칸으로 나뉘어 있고, grid[i][j]는 i행 j열 칸에서 얻는 이익입니다(음수면 손해).
변이 격자선과 나란한 직사각형 영역 하나를 골라 그 안의 모든 칸의 이익을 얻으려고 합니다. 영역은 적어도 한 칸을 포함해야 합니다. 얻을 수 있는 이익 합의 최댓값을 반환하세요.
입출력 예
| grid | result |
|---|---|
[[1, -2, 3], [-4, 5, 6], [7, -8, 9]] | 18 |
[[-5, -2], [-3, -9]] | -2 |
[[2, 3, -100, 4]] | 5 |
입출력 예 설명
예 1 — 맨 오른쪽 열 전체(3 + 6 + 9 = 18)가 가장 큽니다. 격자 전체의 합은 17이고, 오른쪽 아래 2×2 영역은 5 + 6 - 8 + 9 = 12입니다.
예 2 — 모든 칸이 음수이므로 가장 덜 손해인 칸 하나(-2)를 고릅니다.
예 3 — 가운데의 -100을 피해 왼쪽 두 칸(2 + 3 = 5)을 고릅니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(grid: int[][]) → long
제한 사항
-
grid.length,grid[i].length(모든 행의 길이는 같습니다) -
grid[i][j] - 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(R^2 * C)
- 공간
- O(C)
입출력 예
| grid | 기대 출력 |
|---|---|
[[1,-2,3],[-4,5,6],[7,-8,9]] | 18 |
[[-5,-2],[-3,-9]] | -2 |
[[2,3,-100,4]] | 5 |
힌트
힌트
직사각형은 "위쪽 행 top, 아래쪽 행 bottom, 왼쪽 열, 오른쪽 열"로 정해집니다. 네 가지를 모두 고르면 가지입니다.
위·아래 행을 고정하면 남은 문제는 1차원입니다. 열마다 top~bottom 행의 합을 col[j]에 모아 두면,
그 행 범위의 최대 직사각형은 배열 col의 최대 연속 부분합과 같습니다. 이것은 카데인 알고리즘으로 에 구합니다.
for top in 0..R-1:
col = [0] * C
for bottom in top..R-1:
col[j] += grid[bottom][j] (모든 j)
best = max(best, kadane(col))
bottom을 늘릴 때 col에 한 행만 더하면 되므로 전체 입니다. 행보다 열이 적으면 행과 열을 바꿔 생각해도 됩니다.
합은 64비트 정수로 다루세요.
복잡도 목표
2차원 누적 합으로 모든 직사각형을 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 3490 ms | 도출됨 |
| Java 25 | 1034 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |