이전 비용으로 다음 칸 계산하기

같은 중간 결과를 한 칸에 저장해요

리스트·반복·함수를 배웠어요. 한 칸 또는 두 칸씩 앞으로 이동할 수 있어요. 도착한 칸의 비용을 내야 할 때 같은 위치까지 오는 여러 방법이 있어요. dp[position]에 그 위치까지의 최소 비용을 저장해요.

예제 costs =[4, 2, 5]는 1번 칸 비용 4, 2번 칸 비용 2, 3번 칸 비용 5예요. 출발 0번 칸은 비용 0이에요. dp[0]= 0, dp[1]= 4로 시작해요. 다음 페이지에서 현재 칸의 바로 앞·두 칸 앞이 후보가 되는 것을 확인해요.

두 후보 중 싼 경로에 현재 비용을 더해요

min(a, b)는 두 값 중 작은 값을 반환해요. 2번 칸에는 0번 또는 1번에서 오므로 min(dp[0], dp[1]) + 2인 2가 돼요. 3번은 min(dp[1], dp[2]) + 5인 7이에요.

앞 칸의 dp를 확정한 뒤 뒤 칸을 계산해요. 도착 칸은 건너뛰어 마칠 수 없어요. 비용 값이 아닌 최소 누적 비용을 재사용하는 방법을 동적 계획법 DP라고 해요. n = 0이면 출발이 곧 도착이라 0이에요.

직접 풀어봐요

0번 위치에서 n 번 칸까지 한 번에 1 칸 또는 2 칸 이동해요. 도착하는 각 칸의 비용을 내요. n 번 칸에 정확히 도착하는 최소 총 비용을 출력해요.

첫 줄 n(0100), 다음 n 줄에 1n 번 칸의 비용(0~1000)이에요. n = 0의 답은 0이에요.

예시 1: costs =[4, 2, 5] → 7. 0 → 2 → 3으로 가요. 예시 2: costs =[3, 8, 1, 2] → 6. 0 → 1 → 3 → 4로 가요.

3
4
2
5

7

4
3
8
1
2

6