Lv.2dpgrid
통행료가 가장 적은 길
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
바둑판처럼 나뉜 마을 지도 grid가 있습니다. 칸 (i, j)를 지나가려면 통행료 grid[i][j]를 내야 합니다.
여행자는 왼쪽 위 칸 (0, 0)에서 출발해 오른쪽 아래 칸 (H-1, W-1)까지 가려고 합니다. 한 번에 오른쪽 또는 아래쪽으로 한 칸씩만 움직일 수 있습니다.
출발 칸과 도착 칸을 포함해, 지나는 모든 칸의 통행료 합이 최소가 되도록 갈 때 그 최소 합을 반환하세요.
입출력 예
| grid | result |
|---|---|
[[1, 3, 1], [1, 5, 1], [4, 2, 1]] | 7 |
[[1, 2, 3], [4, 5, 6]] | 12 |
[[5]] | 5 |
입출력 예 설명
예 1 — 오른쪽, 오른쪽, 아래, 아래로 가면 1 + 3 + 1 + 1 + 1 = 7입니다.
예 2 — 윗줄을 끝까지 간 뒤 내려가면 1 + 2 + 3 + 6 = 12로 가장 적습니다.
예 3 — 출발 칸이 곧 도착 칸입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(grid: int[][]) → int
제한 사항
- , (
grid는 직사각형) -
grid[i][j]
기대 복잡도
- 시간
- O(HW)
- 공간
- O(W)
입출력 예
| grid | 기대 출력 |
|---|---|
[[1,3,1],[1,5,1],[4,2,1]] | 7 |
[[1,2,3],[4,5,6]] | 12 |
[[5]] | 5 |
힌트
힌트
어떤 칸 (i, j)에 들어오는 방법은 위 칸에서 내려오거나 왼쪽 칸에서 오는 두 가지뿐입니다. 따라서
이고, 첫 줄과 첫 열은 한 방향에서만 들어올 수 있습니다.
가능한 모든 경로를 재귀로 따라가면 경로 수가 개로 폭발해 효율성 테스트를 통과할 수 없습니다. 위 식으로 표를 위에서 아래, 왼쪽에서 오른쪽 순으로 채우면 이며, 한 줄만 기억해도 충분합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1040 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |