[BOJ] 주유소 in Python

박준규·2021년 12월 28일
0

알고리즘

목록 보기
9/39

문제풀러가기!

이 문제는 그렇게 어려운 문제는 아니었습니다. 그렇기 때문에 엄청 쉽게 접근했습니다.

문제 풀이 포인트
문제에서 주어지는 2개의 배열 중에서 마지막 주요소의 가격은 어차피 사용을 못합니다. 그래서 그냥 데이터 받고 pop해주었습니다. 어차피 쓸모 없으니까요! 물론 안해줘도 별로 상관없습니다.

제가 푼 문제의 포인트는 다음과 같아요.

  1. 보다 더 작은 주유비가 드는 곳에서 주유만 하면 됩니다.
  2. 그러기 위해선i번째 까지의 최소 비용을 찾아야 합니다.
    • 문제에서 이야기한 최대 주유 비용인 10억보다 1 더 큰 숫자를 처음에 지정한 후 더 작은 숫자를 업데이트 해 가면 됩니다. i번째 까지의 최소 비용을 알 수 있습니다.
  3. 이제 O(n)을 순회하면서 최소 주유 비용을 업데이트 하면서 업데이트가 되지 않으면 원래 최소 비용에서 거리를 곱한 값을 더해줍니다. 업데이트가 되면 이러한 연산과정에서 바뀐 최소 비용으로 더해주면 됩니다.

아래는 제가 짠 코드입니다.

import sys
n = int(input())
distance = list(map(int, sys.stdin.readline().split()))
cost = list(map(int, sys.stdin.readline().split()))

cost.pop()

more_small = 1000000001
answer = 0

for d, c in zip(distance, cost):
    if more_small > c:
        more_small = c
        answer += (more_small*d)
    else: answer += (more_small*d)

print(answer)
profile
'개발'은 '예술'이고 '서비스'는 '작품'이다

0개의 댓글