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()
ps/problems/boj/13305.txt · 마지막으로 수정됨: 2024/02/08 03:37 저자 teferi
토론