dovelet/problems/race1

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). binary indexed tree(http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree)를 사용한다면 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])