[C++] 백준 13305번 주유소

1. 문제이해

13305번: 주유소 (acmicpc.net)

13305번: 주유소

 

N개의 도시들이 서로 수평적으로 이어져 있다고 가정하자.

제일 왼쪽에서 제일 오른쪽의 도시로 가는데 드는 기름값의 비용을 구하려고 할 때,

1km 당 1L의 기름값이 들며, 도시별로 기름값은 상이하다.

이때, 도시의 개수와 각 도시에서의 기름값, 도시 사이의 거리를 입력받아

제일 왼쪽 도시에서 오른쪽 도시로 가는 최소비용을 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

그리디 알고리즘의 일종이다.

그리디 알고리즘이란, 현재 내가 선택할 수 있는 선택지 중 가장 나은 선택지를 선택해 나가는 알고리즘이다.

이 문제는 해당 지점에서 다음 기름값이 더 싼지, 비싼지를 선택해 나가며 최소비용을 구해야 한다.

예제 1의 경우, 최소비용을 구하는 방법은 다음과 같다.

 

 

글보다는 그림을 그리고 직접 쓰는게 전달이 잘 될것 같아서 설명을 써보았다.

(실제로도 쓰면서 방법을 도출하긴 하는데, 올릴거라서 예쁘게 정리해보았다.☺)

 

위 그림과 같이 현재 최소인 기름값과, 다음 기름값을 비교하여

더 작은 기름값을 통해 도시를 건너가면 되는 형식이다.

주의할 점은 위 그림처럼

1.첫 번째 디폴트값(1 > 2로 가는데는 꼭 1에서 충전을 해야함)을 설정해야 한다는 것과,

2. 마지막 지점의 기름값은 무시해주어야 한다는 것,

그리고 마지막으로 주의해야 할 점은, 실제 코딩을 해보면 기름값이  1,000,000,000까지로

범위가 매우 크기때문에 3.long long 형을 써주어야 한다는 점이다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;
long long oil_price[100000];
long long road[100000];

int main() {
	long long city;
	long long min;
	long long total;

	cin >> city;	// 도시의 개수

	for (int i = 0; i < city - 1; i++) {
		cin >> road[i];	// 각 도로의 km
	}

	for (int i = 0; i < city; i++) {
		cin >> oil_price[i];	// 각 도시에서의 기름값
	}

	min = oil_price[0];
	// 첫번째 > 두번째 도시로 갈때는 무조건 첫번째에서 충전 후 출발
	total = min * road[0];	

	for (int i = 0; i < city; i++) {
		if (min >= oil_price[i + 1]) {	// 기름값이 작은 경우를 계속 확인해나감
			min = oil_price[i + 1];	// 최솟값 변경시 새로 설정
		}
		// 해당 지점에서의 최소기름값 * 다음 도시까지의 길이
		total += min * road[i + 1];
	}
	// 마지막 도시에서의 기름값은 어차피 다음 도시까지의 길이가 없으므로
    	// 자동으로 무시가 된다.
    
	cout << total;

	return 0;
}

구현한 코드는 위와 같았다.

우선, 도시의 개수(city), 각 도시 사이의 거리(road[i]), 도시에서의 기름값(oil_price[i])을 입력받는다.

이후, 최소 기름값은 첫 도시의 기름값(oil_price[0])으로 초기화 해주고, 

첫번째 도시에서 두번째 도시로 갈 때에는 무조건 첫번째 도시에서 충전을 하고 출발해야 하므로,

총 비용인 total의 값을 min(여기서는 oil_price[0]) * road[0] 값으로 초기화 했다.

 

다음 for문을 통해 해당 지점에서의 가장 작은 기름값(min)을 찾아 갱신해나가면서,

해당 지점에서의 가장 작은 기름값 * 다음 도시까지의 길이 (min * road[i + 1])를

총 기름값 비용에 더해나간다.

 

주석 없는 코드는 왼쪽 아래 더보기를 참고바랍니다.😊

<주석 없는 코드>

#include <iostream>
using namespace std;
long long oil_price[100000];
long long road[100000];

int main() {
	long long city;
	long long min;
	long long total;

	cin >> city;	

	for (int i = 0; i < city - 1; i++) {
		cin >> road[i];	
	}

	for (int i = 0; i < city; i++) {
		cin >> oil_price[i];	
	}

	min = oil_price[0];
	total = min * road[0];	

	for (int i = 0; i < city; i++) {
		if (min >= oil_price[i + 1]) {	
			min = oil_price[i + 1];
		}
		
		total += min * road[i + 1];
	}
    
	cout << total;

	return 0;
}

 

 

---

그리디 알고리즘 유형들을 위주로 풀어보려고 하는데..

그리디 알고리즘 유형이 아직 익숙치 않아서 그런지, 규칙을 찾아내는데 까지 시간이 조금 걸렸다.😥

여러 유형들로 많이 풀어보는게 중요할 것 같다.