More actions
imported>skywave No edit summary |
(Repair batch-0008 pages from live compare) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
http://183.106.113.109/30stair/race1/race1.php | |||
== 조영준 == | == 조영준 == | ||
=== 분석 === | === 분석 === | ||
f(n) = (n번 째 station까지 지나갈 때의 시간의 최솟값. n번 째 station은 반드시 방문) | f(n) = (n번 째 station까지 지나갈 때의 시간의 최솟값. n번 째 station은 반드시 방문) | ||
g(n) = (n번 째 station을 방문 할 때 소요되는 시간) | g(n) = (n번 째 station을 방문 할 때 소요되는 시간) | ||
문제에서는 n개의 station 정보( | 문제에서는 n개의 station 정보( | ||
f(0), ... f(n - 1) | f(0), ... f(n - 1) | ||
)만 주지만, 마지막 station의 방문 소요 시간( | )만 주지만, 마지막 station의 방문 소요 시간( (f(n))을 0으로 기록해두자. | ||
n번 째 station에서 다른 station을 방문하지 않고 가장 뒤로 멀리 갈 수 있는 station을 m이라고 하면 | n번 째 station에서 다른 station을 방문하지 않고 가장 뒤로 멀리 갈 수 있는 station을 m이라고 하면 | ||
| Line 17: | Line 18: | ||
시간 복잡도는 | 시간 복잡도는 | ||
O(n^2) | O(n^2) | ||
. [http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree binary indexed tree]를 사용한다면 | . [http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree binary indexed tree]를 사용한다면 O(nlogn)까지 기대. | ||
주의사항으로는, 마지막 10번 input data는 자기 멋대로 | 주의사항으로는, 마지막 10번 input data는 자기 멋대로 | ||
| Line 27: | Line 28: | ||
case_limit = int(input()) | case_limit = int(input()) | ||
case_length = int(input()) | case_length = int(input()) | ||
case_distance = | case_distance = [int(x) for x in input().split()] + [0] | ||
case_time = | case_time = [int(x) for x in input().split()] + [0] | ||
list_time = | list_time = [0] | ||
for i in range(0, case_length + 1): | for i in range(0, case_length + 1): | ||
distance = case_distance | distance = case_distance[i] | ||
left_index = i | left_index = i | ||
while left_index > 0 and distance + case_distance | while left_index > 0 and distance + case_distance[left_index - 1] <= case_limit: | ||
left_index -= 1 | left_index -= 1 | ||
distance += case_distance | distance += case_distance[left_index] | ||
list_time.append(min(list_time | list_time.append(min(list_time[left_index:i + 1]) + case_time[i]) | ||
print(list_time | print(list_time[-1]) | ||
Latest revision as of 01:40, 27 March 2026
조영준
분석
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를 사용한다면 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])