BOJ 133051 [python] BOJ 13305 주유소 백준 13305번 주유소 그리디 알고리즘의 대표적인 문항인 13305번 주유소 문제이다. 길게 써져있지만 요약하면, 동그라미안의 숫자는 1L당 가격이고 사이 숫자는 거리를 나타낸 것이다. 각 도시에서는 최소한 다음 도시까지 갈 기름을 구매해야한다. 즉 도시에서 도시사이의 거리는 기름에 대한 최소 조건이 된다. 직관적으로 가장 싸게 이동하려면, 기름 가격이 비싼 곳에서는 최소 필요 기름만큼만 구매하고 기름 가격이 저렴한 곳에서는 최대한 많이 구매하면 된다. 풀이 예시를 한번 가져와보자. 4개의 도시에서 각 도시 사이의 거리는 2 , 3 ,1 이고 각 도시의 L당 기름 값은 5, 2, 4, 1 이다. 사실 문제를 잘 읽으면 알 수 있는것이 마지막 도시의 기름 값은 고려할 필요가 없다. 최소 비용이 도출되는 .. 2021. 8. 18. 이전 1 다음
