사용자 도구

사이트 도구


ps:problems:boj:13305

주유소

ps
링크acmicpc.net/…
출처BOJ
문제 번호13305
문제명주유소
레벨실버 4
분류

그리디

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python
제출기록46788KB / 104ms
최고기록92ms
해결날짜2022/02/08

풀이

  • 그리디의 대표적인 유형중 하나. 주유소 문제 참고.
  • 이러한 문제는 현재 주유소에서 넣어야 하는 기름의 양을 즉시 결정하는 대신에, 일단 안 넣었다 치고서 시뮬레이션 하다가 나중에 필요해지면, 그제서야 아까 넣었던걸로 처리하는 것이 요령이다. 여기에서는 지나온 주유소중 가장 기름이 싼 주유소만 기억하고 있다가, 기름이 부족해지면 아까 그 주유소에서 기름을 샀던걸로 처리하는 방식으로 구현하면 된다.
  • 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 13305. 주유소".

- Problem link: https://www.acmicpc.net/problem/13305
- Solution link: http://www.teferi.net/ps/problems/boj/13305

Tags: [Greedy]
"""

INF = float('inf')


def main():
    N = int(input())  # pylint: disable=unused-variable
    distances = [int(x) for x in input().split()]
    prices = [int(x) for x in input().split()]

    min_price = INF
    answer = 0
    for price, distance in zip(prices, distances):
        if price < min_price:
            min_price = price
        answer += min_price * distance

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Y J N O I
 
ps/problems/boj/13305.txt · 마지막으로 수정됨: 2024/02/08 03:37 저자 teferi