Funcia
Lv.2dpgrid

통행료가 가장 적은 길

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

바둑판처럼 나뉜 마을 지도 grid가 있습니다. 칸 (i, j)를 지나가려면 통행료 grid[i][j]를 내야 합니다.

여행자는 왼쪽 위 칸 (0, 0)에서 출발해 오른쪽 아래 칸 (H-1, W-1)까지 가려고 합니다. 한 번에 오른쪽 또는 아래쪽으로 한 칸씩만 움직일 수 있습니다.

출발 칸과 도착 칸을 포함해, 지나는 모든 칸의 통행료 합이 최소가 되도록 갈 때 그 최소 합을 반환하세요.

입출력 예

gridresult
[[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

제한 사항

  • 1≤H≤7001 \le H \le 700, 1≤W≤7001 \le W \le 700 (grid는 H×WH \times W 직사각형)
  • 0≤0 \le grid[i][j] ≤9,999\le 9{,}999

기대 복잡도

시간
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)에 들어오는 방법은 위 칸에서 내려오거나 왼쪽 칸에서 오는 두 가지뿐입니다. 따라서

best[i][j]=grid[i][j]+min⁡(best[i−1][j], best[i][j−1])best[i][j] = grid[i][j] + \min(best[i-1][j],\ best[i][j-1])

이고, 첫 줄과 첫 열은 한 방향에서만 들어올 수 있습니다.

가능한 모든 경로를 재귀로 따라가면 경로 수가 (H+W−2H−1)\binom{H+W-2}{H-1}개로 폭발해 효율성 테스트를 통과할 수 없습니다. 위 식으로 표를 위에서 아래, 왼쪽에서 오른쪽 순으로 채우면 O(HW)O(HW)이며, 한 줄만 기억해도 충분합니다.

언어별 시간 제한

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

테스트 그룹

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

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