문제 1027 · 중급 5

징검다리 출근길

다이나믹 프로그래밍

테스트별 제한 1500ms · 브라우저 채점

문제

비 온 다음 날 출근길 개울에 징검다리 돌 N개가 한 줄로 놓여 있다. 1번 돌에서 출발해 N번 돌에 도착해야 한다. 한 번에 1칸, 2칸, 3칸 앞의 돌로 건너뛸 수 있고 뒤로는 가지 않는다. 돌마다 미끄러운 정도 c_i 가 있어서 그 돌을 밟으면 c_i 만큼 힘이 든다. 출발하는 1번 돌과 도착하는 N번 돌도 밟은 것으로 친다. 흔들리는 돌은 -1 로 표시되어 있고 절대 밟으면 안 된다. N번 돌까지 가는 데 드는 힘의 합의 최솟값을 구하라. 갈 수 없으면 -1 을 출력한다.

입력

첫째 줄에 돌의 수 N (2 ≤ N ≤ 50,000) 이 주어진다.

둘째 줄에 c_1 … c_N 이 주어진다. c_i 는 -1 이거나 0 이상 1,000 이하의 정수다. c_1 과 c_N 은 -1 이 아니다.

출력

힘의 합의 최솟값을 출력한다. 갈 수 없으면 -1 을 출력한다.

예제 입력 1

6
2 5 -1 1 9 3

예제 출력 1

예제 입력 2

5
1 -1 -1 -1 1

예제 출력 2

-1

힌트 펼치기

best[i] 를 'i번 돌에 서기까지 드는 최소 힘' 이라 하면 best[i] = min(best[i−1], best[i−2], best[i−3]) + c_i 다.
흔들리는 돌과 도달할 수 없는 돌은 '무한대' 로 두면 식을 그대로 쓸 수 있다.

풀이 작성

코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.

풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.

로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.