http://183.106.113.109/30stair/race1/race1.php
== 조영준 ==
=== 분석 ===
{{{f(n) = (n번 째 station까지 지나갈 때의 시간의 최솟값. n번 째 station은 반드시 방문)}}}
{{{g(n) = (n번 째 station을 방문 할 때 소요되는 시간)}}}
문제에서는 n개의 station 정보({{{f(0), ... f(n - 1)}}})만 주지만, 마지막 station의 방문 소요 시간({{{(f(n)}}})을 0으로 기록해두자.

n번 째 station에서 다른 station을 방문하지 않고 가장 뒤로 멀리 갈 수 있는 station을 m이라고 하면 {{{f(n) = min(f(m), f(m + 1), ... f(n - 1)) + g(n)}}} 이 성립한다.

계산을 마치면 {{{f(n)}}}이 답.

시간 복잡도는 {{{O(n^2)}}}. [http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree binary indexed tree]를 사용한다면 {{{O(nlogn)}}}까지 기대.

주의사항으로는, 마지막 10번 input data는 자기 멋대로 {{{\n}}}으로 중간에 input을 잘라버린다. 아래 코드처럼 line 단위로 입력을 받는 경우 터짐. 도블릿을 깝시다.

=== 코드(python3) ===
10번 input data의 경우 dovelet에서 임의로 input에 대해 line wrap을 해버리기 때문에 입력을 제대로 받지 못해서 틀려버린다. 주의.
{{{
case_limit = int(input())
case_length = int(input())
case_distance = [int(x) for x in input().split()] + [0]
case_time = [int(x) for x in input().split()] + [0]

list_time = [0]

for i in range(0, case_length + 1):
    distance = case_distance[i]
    left_index = i

    while left_index > 0 and distance + case_distance[left_index - 1] <= case_limit:
        left_index -= 1
        distance += case_distance[left_index]

    list_time.append(min(list_time[left_index:i + 1]) + case_time[i])

print(list_time[-1])
}}}