[백준/c++] - 13305 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

매 순간 마다 최선의 것을 택해서 최소 혹은 최대의 것을 구하는

그리디 알고리즘 문제 입니다.

 

처음에는 dfs나 dp등 다른 방법으로 구현이 가능할 것 같았지만,

문제에 제시된 조건에 도시의 수가 이 방법으로는 시간 초과가 날 것같아

그리디 알고리즘으로 구하려고 방향을 바꿨습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main() {

	int city_int;
	vector<int>roads(100000, 0);
	vector<int>soil_prices(100000, 0);

	int ans = 0;

	cin >> city_int;

	int tmp = 0;
	
	//처음 도시 까지의 거리는 0 = 출발 지점
	for (int i = 1; i < city_int; i++) { // 길의 길이 입력
		cin >> roads[i];
	}

	for (int i = 0; i < city_int; i++) { // 기름값 입력
		cin >> soil_prices[i];
	}

	int cur_location = 0; // 현재 지나온 도시의 개수를 반영 출발 시에 0
	while (cur_location != city_int - 1) { // 지나온 도시의 개수 == 전체 도시의 개수 -1 일때 종료

		int cur_location_cpy = city_int; // 현재 위치 기록
		for (int i = cur_location + 1; i < city_int; i++) { // 다음 도시와 현재 도시 비교

			if (soil_prices[cur_location] > soil_prices[i]) { // 현재 도시 보다 기름이 싼 다음 도시 존재 시

				int distance = 0;

				for (int j = cur_location + 1; j < i + 1; j++) { // 그 도시까지의 거리
					distance += roads[j];
				}

				ans = ans + (distance * soil_prices[cur_location]); // 더 싼 도시까지 현재 도시에서 기름 넣고 이동
				cur_location = i; // 현재 위치 이동
				break; // 이동 후 반복문 종료
			}

		}

		if (cur_location == city_int) { // 이동 못함 -> 현재 도시가 가장 싼 경우
			int distance = 0;
			for (int i = cur_location; i < city_int; i++) {
				distance += roads[i];
			}

			ans = soil_prices[cur_location] * distance;
			break;
		}

		
	}

	cout << ans;
	return 0;
}

처음에 짰던 코드는 위와 같습니다.

 

문제를 풀 때 이런식으로 메모장에 정리해서 최대한 코드로 구현이 용이하도록 정리하여 구현했습니다.

 

처음 생각은 이랬습니다.

현재도시에서 목적지까지 미리 기름값을 조사해서 현재 도시보다 싸면서 가장 가까운 도시까지 한번에 이동

하는 것이 시간을 단축 할 수 있을거라고 판단하여 위와 같이 코드를 구현하였습니다.

 

하지만 그게 아니였습니다.

 

이 코드를 이용하면 문제를 풀 수는 있으나 시간초과가 뜹니다.

 

이유를 나름대로 생각을 해보았고, 이코드는 확실히 시간초과가 날 만한 이유가 있었습니다.

예를 들어 출발하는 도시의 기름값이 가장 싼경우, 첫번째 반복문에서 끝까지 조사를 하고,

이는 if 조건문에서 이동을 하지 못한 경우에 해당하여 그 곳까지의 거리를 구하기 위해,

도시의 개수 city_int 만큼 한번더 반복문을 돌립니다.

 

현재 도시보다 싼 도시를 찾아서 한번에 이동한다는 알고리즘이 오히려

한번에 하나씩 이동하는 알고리즘보다 시간이 오래 걸려버리는 아이러니한 상황이게 된 것입니다...

 

결국 이를 토대로 다시 코드를 바꿨습니다.

 

#include <iostream>
#include <vector>

using namespace std;


int main() {

	long long city_int;
	vector<long long>roads(100000, 0);
	vector<long long>soil_prices(100000, 0);

	long long ans = 0;

	cin >> city_int;


	for (int i = 1; i < city_int; i++) { // 길의 길이 입력
		cin >> roads[i];
	}

	for (int i = 0; i < city_int; i++) { // 기름값 입력
		cin >> soil_prices[i];
	}

	
	int cheap_price_inx = 0; // 현재 지난 도시중 가장 싼 곳
	for (int i = 1; i < city_int; i++) {

		if (soil_prices[cheap_price_inx] > soil_prices[i]) { // 다음 도시가 지나온 도시들 보다 더 싸다면

			ans = ans + (roads[i] * soil_prices[cheap_price_inx]); // 다음 도시 까지 이동 후
			cheap_price_inx = i; // 최소 기름 값 갱신, 다음 이동부터 적용

		}
		else {
			ans = ans + (soil_prices[cheap_price_inx] * roads[i]);
		}

	}


	cout << ans;
	return 0;
}

이는 인터넷에서 본 힌트를 참고하여 최대한 간단하게 표현해본 코드 입니다. (훨씬 간편해져서 무안...)

 

한번에 하나씩 이동을 하고, 현재 가장 싼 기름값을 계속 유지 하면서, 다음 도시의 기름값이 싸다면

지불할 기름값을 그 도시의 기름값으로 갱신하는,

다시 말해, 단순히 최솟값을 갱신하면서 한칸씩 나아가는 알고리즘 입니다. 시간 복잡도로 따지면 O(N)으로 단순합니다.

 

알고나면 너무나도 간단하지만, 매번 도시에 도착하면 기름값을 바꿔야 한다는

강박관념이 단순한 코드를 짤 수 있는 방법을 생각하지 못하게 했던것 같습니다.

 

이 경우 케이스가 어떻든 O(N) 의 시간 복잡도를 가지며, 시간초과가 나지 않습니다.

 

공부하면 할수록 겸손해지는 알고리즘 문제풀이...