[G2] 백준 1826번 연료 채우기 C++ 그리디 알고리즘, 우선순위 큐

리뷰

 

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

우선순위 큐 2개를 사용해서 마을에 도달하기 까지 최소한의 주유소 방문 횟수를 구하는 문제

 

 

전역 변수

• n : 주유소의 개수를 저장할 변수
• ans : 주유소 방문 횟수를 저장할 변수
• Station : 주유소 위치와 채울 수 있는 연료의 양을 정의할 구조체, 위치를 기준으로 오름차순 정렬한다.

 

함수

없음

 

 

문제풀이

1. Station타입의 우선순위 큐 pq1을 초기화 한다.
2. n값을 입력 받고, n개의 주유소 위치와 채울 수 있는 연료의 양을 pq1에 추가한다.
3. 정수형의 우선순위 큐 pq2를 초기화한다.
4. l, p값을 입력 받고, pq1에서 p이하에 위치한 주유소를 꺼내 충전량을 pq2에 추가한다.
5. p가 l보다 작으면서 pq2가 비지 않았다면 while루프를 수행한다.
6. 매 루프마다 ans를 증가시키고, p에 pq2의 top을 더해준 뒤 pq2에서 요소를 제거한다.
7. pq1에서 갱신된 p이하에 위치한 주요소를 꺼내 충전량을 pq2에 추가한다.
8. while루프가 종료된 후에도 p가 l보다 작다면 -1을, 아니라면 ans를 출력한다.

 

트러블 슈팅

1. while루프가 종료되었을때 p가 l보다 큰지 여부를 구분하여 출력하지 않아 WA를 받았다.
2. p가 l보다 작을 경우 ans가 아닌 -1을 출력하게 변경하여 AC를 받았다.

 

참고 사항

1. 모든 주유소와 마을은 서로 다른 좌표에 있고, 마을은 모든 주유소보다 오른쪽에 있다.
2. b(1 ≤ b ≤ 100), L(1 ≤ L ≤ 1,000,000), P(1 ≤ P ≤ 1,000,000)로 long long타입을 고려할 필요가 없다.

 

정답 코드

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

int n, ans;
struct Station {
	int x, c;
	bool operator<(const Station& other) const {
		return x > other.x;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	priority_queue<Station> pq1;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, c; cin >> x >> c;
		pq1.push({ x, c });
	}

	priority_queue<int> pq2;
	int l, p; cin >> l >> p;
	while (!pq1.empty() && pq1.top().x <= p) {
		pq2.push(pq1.top().c);
		pq1.pop();
	}

	while (p < l && !pq2.empty()) {
		ans++;
		p += pq2.top();
		pq2.pop();

		while (!pq1.empty() && pq1.top().x <= p) {
			pq2.push(pq1.top().c);
			pq1.pop();
		}
	}

	cout << (p < l ? -1 : ans);
}