글 읽기 - 파이썬 시간초과가 뜹니다.

bsmbaek 3년 전 0

생각한 방법은 기름값이 제일싼 위치를 찾고 그 이후의 거리를 이용해 비용을 구하고

계산된 뒤쪽은 날려버린채

다시 가장싼 가격을 찾는 방식으로 진행했습니다.

어떻게 하면 시간을 줄여볼 수 있을까요

도움 주시면 감사하겠습니다!

num = int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))
ans = 0

while len(distance)>0:
    i = price.index(min(price[:-1]))
    
    cost = sum(distance[i:]) * price[i]
    price = price[:i+1].copy()
    distance = distance[:i].copy()
    
    
    ans +=cost
    
print(ans)

orb_of_zone 3년 전 0

주어진 방식대로 하면 최악의 경우 O(n²) 만큼 연산하게 됩니다. 아래와 같은 경우를 생각해보세요.

----

100000

1 2 3 ... 99999

1 1 1 .... 1

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간초과가 뜹니다.

bsmbaek 3년 전 0

orb_of_zone 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말