캠핑장 야간 통로

문제

캠핑장 관리인은 밤이 되기 전에 입구에서 출구까지 이동하며 통로의 상태를 확인해야 한다. 통로에는 일렬로 놓인 N개의 지점이 있다. 입구의 위치를 0, 통로 안의 지점들을 입구에서 가까운 순서대로 1부터 N, 출구의 위치를 N+1이라고 한다. 관리인은 처음에 입구에 있으며, 한 번 이동할 때 현재 위치보다 번호가 정확히 1 또는 2 큰 위치로 이동할 수 있다. 뒤로 이동하거나 같은 위치에 머무는 이동은 허용하지 않는다. 각 지점에는 이동을 돕는 임시 발판이 있거나, 안전 점검 때문에 출입을 막는 표지가 있다. 발판이 있는 지점에는 0부터 9까지의 정수가 적혀 있다. 관리인이 그 지점에 도착하면 적힌 수만큼의 정비 비용을 지불해야 한다. 비용이 0인 발판도 정상적으로 이용할 수 있다. 출입을 막은 지점에는 도착할 수 없으며, 그 지점에서 출발할 수도 없다. 번호가 2 큰 위치로 이동할 때 중간 지점에는 도착하지 않는다. 따라서 중간 지점의 비용을 내지 않으며, 중간 지점이 막혀 있어도 그 위를 건너갈 수 있다. 다만 한 번에 번호가 3 이상 큰 위치로 이동할 수는 없다. 입구와 출구는 항상 이용할 수 있고, 두 위치에서는 비용이 발생하지 않는다. 출구를 지나친 위치로 이동하는 것은 허용하지 않는다. 통로의 상태는 길이가 N인 문자열로 주어진다. 왼쪽에서 i번째 문자가 숫자이면 i번 지점의 비용을 뜻하고, 대문자 X이면 그 지점이 막혀 있음을 뜻한다. 관리인은 이 상태가 바뀌지 않는 동안 이동한다. 모든 발판을 방문할 필요는 없으며, 이동 횟수를 최소화할 필요도 없다. 목적은 출구에 도착할 때까지 지불한 비용의 합을 최소화하는 것이다. 같은 최소 비용을 만드는 이동 방법이 여러 개여도 비용만 출력한다. 이동 규칙을 지키며 출구에 도달할 수 없다면 -1을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 통로 안의 지점 수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 200,000)
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 숫자 0부터 9 중 하나 또는 대문자 X이다. 문자열에는 공백이 없다.

출력

입구에서 출구까지 이동하는 데 필요한 최소 비용을 정수로 한 줄에 출력한다. 출구에 도달할 수 없으면 -1을 출력한다.

5
2X130

3

3
XXX

-1

1
9

0

출처: Devin.KR 자체 제작