[BOJ] 13305 주유소 - 그리디 알고리즘.
글 작성자: Sowhat_93
매우 간단한 문제이다.
배열을 순회하며 도시를 지날때마다 요금을 정산하는 식으로 한다.
우선 바로 이전 도시에서 해당 도시까지 달린 요금을 정산한다.
물론 저장된 최저기름값으로 한다.
이러면 기름값이 가장 싼 도시에서 미리 주유한것과 같다.
해당 도시의 기름값이 더 싸다면
최저기름값을 업데이트하고,
다음도시로 향하면 된다.
#include <iostream> int NumOfCity = 0; unsigned long long GasPrice [100001] = { 0 , }; unsigned long long DistanceToNextCity [100001] = { 0 , }; int main() { std::cin.sync_with_stdio(false); std::cout.sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); std::cin >> NumOfCity; for (int i = 1; i < NumOfCity; ++i) std::cin >> DistanceToNextCity[i]; for (int i = 1; i <= NumOfCity; ++i) std::cin >> GasPrice[i]; unsigned long long Ans = 0; unsigned long long LowestPrice = 0x7fffffffffffffff; unsigned long long TempDistance = 0; GasPrice[NumOfCity] = 0; for (int i = 1; i <= NumOfCity; ++i) { TempDistance += DistanceToNextCity[i - 1]; if (LowestPrice > GasPrice[i]) { Ans += TempDistance * LowestPrice; LowestPrice = GasPrice[i]; TempDistance = 0; } } std::cout << Ans << '\n'; return 0; }
이 글은
(새창열림)
본 저작자 표시 규칙 하에 배포할 수 있습니다. 자세한 내용은 Creative Commons 라이선스를 확인하세요.
Creative Commons
본 저작자 표시
'알고리즘' 카테고리의 다른 글
[BOJ] 1037 약수 - 정수론 (0) | 2022.02.07 |
---|---|
[BOJ] 5086 배수와 약수 (0) | 2022.02.07 |
[BOJ] 1541 잃어버린 괄호 - 그리디 알고리즘 (0) | 2022.02.06 |
[BOJ] 11399 ATM - 그리디 알고리즘 (0) | 2022.02.06 |
[BOJ] 11047 동전 0 - 그리디 알고리즘 (0) | 2022.02.06 |
댓글
이 글 공유하기
다른 글
-
[BOJ] 1037 약수 - 정수론
[BOJ] 1037 약수 - 정수론
2022.02.07 -
[BOJ] 5086 배수와 약수
[BOJ] 5086 배수와 약수
2022.02.07 -
[BOJ] 1541 잃어버린 괄호 - 그리디 알고리즘
[BOJ] 1541 잃어버린 괄호 - 그리디 알고리즘
2022.02.06 -
[BOJ] 11399 ATM - 그리디 알고리즘
[BOJ] 11399 ATM - 그리디 알고리즘
2022.02.06
댓글을 사용할 수 없습니다.