백준 13305 : 주유소(그리디)

https://www.acmicpc.net/problem/13305

13305번: 주유소

문제 요약:

어떤 나라에 일직선 도로 위에 N개의 도시가 있다.

차로 이동하려고 한다. 기름통의 크기는 무제한, 1키로에 1리터 사용.

도시마다 단 하나의 주유소가 있으며, 주유소의 기름 가격은 상이.

INPUT : 도시에 있는 주유소의 기름 가격, 도로의 길이

OUTPUT: 제일 왼쪽 도시에서 오른쪽 도시로 이동하는 최소의 비용

 

처음 풀이:

58점이 나왔다. 서브태스크 2까지는 도시 갯수가 최대 1000개인데, 그 이상에 대해서 메모리 또는 시간 에러가 난 것 같다. 

def solve(N, lenths, costs):
    tot_cost = 0
    i=0
    if N==1 : return 0
    while i < N-1:
        cheaper = [j for j,e in enumerate(costs) if (costs[i]>e and j>i and j<N-1)]
        cheaper.append(N-1)
        nxt = min(cheaper)
        tot_cost += sum(lenths[i:nxt])*costs[i]  # 현재 있는 곳의 가격으로, 다음 충전소까지 
        i = nxt
    return tot_cost


if __name__=='__main__':
    N = int(input())
    lenths = list(map(int, input().split()))
    costs = list(map(int, input().split()))
    ans = solve(N, lenths, costs)
    print(ans)

 

-----------------

위 복잡도를 N^2에서 N으로 줄이는 방법을 찾았다. 간단한데 아이디어를 떠올리지 못해서 어렵게 돌아서 풀었던 거 같다. 

def solve(N, lenths, costs):
    # cost sort가 우선일 듯..?
    tot_cost = 0
    cost = costs[0]
    for i in range(N-1):
        cost = min(cost, costs[i])
        tot_cost += lenths[i]*cost
    
    return tot_cost


if __name__=='__main__':
    N = int(input())
    lenths = list(map(int, input().split()))
    costs = list(map(int, input().split()))
    ans = solve(N, lenths, costs)
    print(ans)