[BOJ] 13305번 주유소

풀이 소요시간 : 70분

난이도가 실버 3이지만 그리디 알고리즘 유형의 문제다.
코딩테스트 공부를 시작하고나서 탐색문제만 열심히 풀다가 거의 처음으로 풀어본 그리디 문제다.
따라서 기초 문제임에도 많은 시간을 필요로했다. 접근 방식을 기록한다.

완벽하지 않은 접근법

1. 기름 값이 싼 도시 순으로 정렬한다.
2. [ 해당 도시 ~ 측정에 포함되지 않은 마지막 도시 ] 까지의 거리를 주유한다.

내가 10분을 구상하고 1시간 가까이 구현한 원인이 바로 이 접근법이 아닐까 싶다.
정렬 알고리즘을 사용해버리니까 데이터 저장방식이 복잡해지고, 전체적인 구현도 지저분해졌다.
다만 정답으로 통과했으니 논리적으로 틀리지는 않은것 같다.

정석적인 접근법

1. 현재 비용보다 다음 비용이 비싸면 다음 비용을 현재 비용으로 설정한다.
2. 현재 비용이 다음 비용보다 비싸면 다음 주유소까지 현재 비용으로 이동한다.

구현이 매우 깔끔해지고, 논리적으로도 깔끔하다.
어려운 유형인만큼 앞으로도 그리디 알고리즘을 꾸준히 연습해야겠다.

전체 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N;
long long Dist[100001];
long long Cost[100001];


void Input() {

	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		cin >> Dist[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> Cost[i];
	}

}


void Greedy() {

	long long total = 0;
	for (int i = 1; i <= N - 1; i++) {

		if (Cost[i] < Cost[i + 1]) {
			Cost[i + 1] = Cost[i];
		}
		total += (Dist[i] * Cost[i]);

	}
	cout << total << endl;

}


int main() {

	Input();
	Greedy();

}