[백준] 13305번 - 주유소

1차

아이디어

1) 주유소중 가격 최솟값을 찾는다.
2) 그 값을 기준으로 도착지점까지 가격을 계산한다.
3) 위의 과정을 반복하며 시작지점까지 도달하게 한다.

코드

N = int(input())
distance = list(map(int,input().split()))
money = list(map(int,input().split()))[:-1]

result = 0
endIndex = len(distance)

while True:
    minMoney = min(money)
    startIndex = money.index(minMoney)

    for i in range(startIndex, endIndex):
        result += (minMoney * distance[i])

    if startIndex == 0:
        break
    else:
        if startIndex > 1:
            money = money[:startIndex]
            endIndex = startIndex
        else:
            result += money[0] * distance[0]
            break

print(result)

시간초과 발생 -> 반복문을 때려넣었으니..당연한 결과임...매우 비효율적인 코드...

최종

아이디어

굳이 거꾸로 생각할 필요가 없었음...순차적으로 진행하면 됨!!!
minPrice에 주유소 시작 위치의 가격을 넣어준다.
도착 지점까지 계속 거리와 가격을 곱해서 계산을 해주는데, 이때 현재 minPrice보다 더 낮은 가격을 발견하면 그 값으로 치환해준다.

코드

N = int(input())
distance = list(map(int,input().split()))
money = list(map(int,input().split()))[:-1]
minPrice = money[0]
result = minPrice * distance[0]

for i in range(1,N-1):
    if money[i] < minPrice:
        minPrice = money[i]
    result += minPrice * distance[i]
print(result)