두 줄 통행료
실버 II의견: 0
\(2 \times N\) 격자의 각 칸에는 양의 정수 통행료가 적혀 있다. 위쪽 줄을 1행, 아래쪽 줄을 2행이라 하고, 왼쪽부터 \(1, 2, \dots, N\)열이라 하자.
당신은 \((1,1)\) 칸에서 출발해 \((2,N)\) 칸까지 이동한다. 한 칸에서 오른쪽으로 인접한 칸 또는 위아래로 인접한 칸(같은 열의 다른 행)으로만 이동할 수 있다(왼쪽으로는 갈 수 없다).
지나간 모든 칸(출발 칸과 도착 칸 포함)의 통행료 합을 비용이라 할 때, 비용의 최솟값을 구하여라.
- \(1 \le N \le 100\,000\)
- 각 통행료는 \(1\) 이상 \(10^6\) 이하의 정수.
첫 줄에 정수 \(N\)이 주어진다.
둘째 줄에 1행의 통행료 \(N\)개가, 셋째 줄에 2행의 통행료 \(N\)개가 공백으로 주어진다.
최소 비용을 출력한다.
3
1 2 5
4 1 1
5(1,1)=1 → (1,2)=2 → (2,2)=1 → (2,3)=1 경로의 비용은 \(1+2+1+1=5\)로 최소이다.
1
7
3
10열이 하나뿐이므로 \((1,1)=7\)에서 \((2,1)=3\)으로 내려가는 수밖에 없다. 비용은 \(7+3=10\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
두 줄 통행료
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
두 줄 통행료