Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 13305 주유소
문제
어떤 나라에 N개의 도시기 일직선으로 있다. 제일 왼쪽 도시에서 제일 오른쪽의도시로 자동차를 이용하여 이동하려 한다. 인접한 두 도시 사이의 도로는 서로 길이가 다를 수 있으며 도로 길이의 단위는 km이다.
처음 출발할 때 자동차는 기름이 없어 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이므로 얼마든지 많은 기름을 넣을 수 있다.
도로를 이용하여 이동할 경우 1km당 1L의 기름이 필요하다. 각 도시에는 단 하나의 주유소가 있으며 도시마다 주유소의 리터당 가격은 다를 수 있다.
각 도시에 있는 주유소의 기름 가격과 각 도시를 연결하는 도로의 깇이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성해라.
입력
첫번째 줄: 도시의 개수
2번째 줄: 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽부터 차례대로
3번째 줄: 주유소의 리터당 가격
Greedy Algorithm: 탐욕 알고리즘
- 선택의 순간마다 그 순간 최적이라 생각되는 것을 선택해 나가는 방식의 알고리즘
그리디 알고리즘 적용 시 필요 조건
- 탐욕적 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않아야한다.
- 최적 부분 구조: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
코드
그리디 알고리즘 적용 방식
- 현재의 주유소(i번째)의 가격과 이전 주유소(0~(i-1)번째)의 가격 중 최소 가격 비교
- if) 현재 주유소가 가장 저렴한 가격인 경우 최솟값을 변경하고 최솟값(현재 주유소 가격)과 다음 도시 사이의 거리를 곱해 total 가격에 더한다.
- else) 이전 주유소의 가격이 더 저렴한 경우 최솟값(이전 주유소 가격)과 다음 도시 사이의 거리를 곱해 total 가격에 더한다.
