Dovelet/problems/race1 - Revision history

Maintenance script: Repair batch-0008 pages from live compare

2026-03-27T01:40:36Z

Repair batch-0008 pages from live compare

← Older revision		Revision as of 01:40, 27 March 2026
Line 6:		Line 6:
	문제에서는 n개의 station 정보(		문제에서는 n개의 station 정보(
	f(0), ... f(n - 1)		f(0), ... f(n - 1)
	)만 주지만, 마지막 station의 방문 소요 시간(~~{{{~~(f(n)~~}}}~~)을 0으로 기록해두자.		)만 주지만, 마지막 station의 방문 소요 시간( (f(n))을 0으로 기록해두자.

	n번 째 station에서 다른 station을 방문하지 않고 가장 뒤로 멀리 갈 수 있는 station을 m이라고 하면		n번 째 station에서 다른 station을 방문하지 않고 가장 뒤로 멀리 갈 수 있는 station을 m이라고 하면
Line 18:		Line 18:
	시간 복잡도는		시간 복잡도는
	O(n^2)		O(n^2)
	. [http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree binary indexed tree]를 사용한다면 ~~{{{~~O(nlogn)~~}}}~~까지 기대.		. [http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree binary indexed tree]를 사용한다면 O(nlogn)까지 기대.

	주의사항으로는, 마지막 10번 input data는 자기 멋대로		주의사항으로는, 마지막 10번 input data는 자기 멋대로
Line 28:		Line 28:
	case_limit = int(input())		case_limit = int(input())
	case_length = int(input())		case_length = int(input())
	case_distance = [int(x) for x in input().split()] + [0]		case_distance = [int(x) for x in input().split()] + [0]
	case_time = [int(x) for x in input().split()] + [0]		case_time = [int(x) for x in input().split()] + [0]

	list_time = [0]		list_time = [0]

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

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

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

	print(list_time[-1])		print(list_time[-1])

imported>skywave at 01:36, 1 December 2014

2014-12-01T01:36:42Z

← Older revision		Revision as of 01:36, 1 December 2014
Line 1:		Line 1:
			http://183.106.113.109/30stair/race1/race1.php
	== 조영준 ==		== 조영준 ==
	=== 분석 ===		=== 분석 ===

imported>skywave at 12:11, 24 November 2014

2014-11-24T12:11:06Z

← Older revision		Revision as of 12:11, 24 November 2014
Line 1:		Line 1:
	== 조영준 ==		== 조영준 ==
	=== 분석 ===		=== 분석 ===
	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)

imported>skywave at 12:10, 24 November 2014

2014-11-24T12:10:53Z

New page

== 조영준 ==
=== 분석 ===
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])