[백준] 1826 연료 채우기

⚡백준 1826 연료 채우기

• https://www.acmicpc.net/problem/1826

• 냅색 알고리즘을 이용하여 주유소를 방문하는 경우 & 방문하지 않는 경우를 검사한다면
  -> 메모이제이션 cache[연료][주유소]의 크기: 10^6 $*$ 10^5 = 10^11
  -> 메모리 초과

• 그리디 알고리즘으로 접근해야 한다

틀린 풀이

• 현재 연료로 갈 수 있는 거리 내 마을이 없는 경우
  현재 연료로 갈 수 있는 주유소 중 얻을 수 있는 연료양 가장 큰 주유소를,
  얻을 수 있는 연료양이 같다면 가장 가까이 있는 주유소를 선택하는 그리디 알고리즘 설계

• 반례 (https://www.acmicpc.net/board/view/29026)
  input:
  2
  2 3
  4 7
  14 4
  output: -1
  answer: 2

• 두 주유소를 모두 방문한다면 마을까지 이동할 수 있지만,
  현재 설계한 그리디 알고리즘은 갈 수 있는 거리 내의 주유소를 단 한 개만 방문하기 때문에 마을까지 이동할 수 없다

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

int n, L, P;
//주유소[위치] = 얻을 수 있는 연료
int station[1000000] = { 0 };
int cnt = 0;

//갈 수 있는 주유소 정렬
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.second > b.second) return true;
	if (a.second == b.second) 
		return a.first > b.first;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		station[a] = b;
	}
	cin >> L >> P;

	//현재 위치
	int cur = 0;

	while (true) {
		//현재 연료로 갈 수 있는 거리 내 마을 있는 경우
		//종료
		if (cur + P >= L) {
			cout << cnt;
			break;
		}

		//현재 연료로 갈 수 있는 거리 내 마을 없는 경우
		//현재 연료로 갈 수 있는 거리 내 주유소 검사

		//<주유소 위치, 얻을 수 있는 연료양>
		vector<pair<int, int>> possibleStation;
		for (int i = cur + 1; i <= cur + P; ++i) {
			if (station[i] != 0)
				possibleStation.push_back(make_pair(i, station[i]));
		}

		//갈 수 있는 주유소 없는 경우 
		//종료
		if (possibleStation.empty()) {
			cout << -1;
			break;
		}
		
		//갈 수 있는 주유소 있는 경우
		// 1. 얻을 수 있는 연료양 가장 큰 주유소 선택 
		// 2. 얻을 수 있는 연료양이 같다면 가장 멀리 있는 주유소 선택
		sort(possibleStation.begin(), possibleStation.end(), cmp);
		
		P = P - (possibleStation[0].first - cur) + possibleStation[0].second;
		cur = possibleStation[0].first;
		cnt++;
	}

	return 0;
}

⚡풀이

• 현재 지점으로부터 이동하여 갈 수 있는 주유소를 maxheap에 저장하는 것이 아니라,
  현재 지점 & 현재 지점까지 지나쳐온 주유소를 maxheap에 저장한다

• 이미 지나쳐온 주유소이기 때문에 주유소까지 이동하는데 소모되는 연료는 고려할 필요 없이, 주유소를 방문하여 얻을 수 있는 연료만 고려하여 선택하면 된다

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

int n, l, p;
//<방문 지점 위치, 방문 지점에서 얻을 수 있는 연료>
vector<pair<int, int>> stop;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		stop.push_back(make_pair(a, b));
	}
	cin >> l >> p;

	//출발 지점도 방문 지점에 포함
	stop.push_back(make_pair(0, 0));
	//마을도 방문 지점에 포함
	stop.push_back(make_pair(l, 0));
	//지점 위치 좌표 오름차순 정렬
	sort(stop.begin(), stop.end());

	//방문 주유소 수
	int cnt = 0;
	//현재 지점 & 지나쳐온 지점들에서 얻을 수 있는 연료 저장
	priority_queue<int> pastStop;

	int cur = 0;
	while(cur < stop.size()){
		//현재 위치 = 마을 위치가 되면 종료
		if (stop[cur].first == l) {
			cout << cnt;
			return 0;
		}

		pastStop.push(stop[cur].second);
		while (true) {
			//다음 지점으로 이동 가능한 경우
			if (stop[cur].first + p >= stop[cur+1].first) {
				p -= (stop[cur + 1].first - stop[cur].first);
				++cur;
				break;
			}
			//다음 지점으로 이동 불가능한 경우
			else {
				if (pastStop.empty()) {
					cout << -1;
					return 0;
				}
				++cnt;
				p += pastStop.top();
				pastStop.pop();
			}
		}
	}

	return 0;
}