[G4] 백준 1744번 수 묶기 C++ 그리디 알고리즘, 우선순위 큐

리뷰

 

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

처음엔 백트래킹을 통한 완전 탐색을 통해 구현하였지만 N값이 50이라 당연하게도 시간 초과가 났다.

이후 우선순위 큐를 사용해 그리디하게 구현하였고, 음수끼리 묶은 경우 양수가 나오는 점을 그리디하게 수정하였더니 AC를 받게 되었다.

 

 

전역 변수

• n : 수열의 길이를 저장할 변수
• ans : 정답을 저장하고 출력하기 위한 변수
• p : 1이상의 수를 저장하기 위한 우선순위 큐
• m : 0이하의 수를 저장하기 위한 우선순위 큐

 

함수

없음

 

 

문제풀이

1. n을 입력받고 n개의 원소를 정수형 변수 num에 입력 받아준다.
2. 만약 num이 0이하라면 m에, 1이상이라면 p에 push를 해준다.
3. p가 빌 때까지 루프를 돌며 정수형 변수 num에 p의 top인 요소를 뽑아준다.
4. 뽑은 후에도 p가 비지 않았다면 정수형 변수 tied에 num과 p의 top값을 곱한 값을 저장해 준다.
5. 만약  tied가 num + p의 top값보다 더 크다면 ans에 tied를 더해주고 p에서 요소를 하나 더 빼준다.
6. 아닐 경우 그냥 뽑은 정수 num을 ans에 더해준다.
7. p가 빌때 까지 위 로직을 수행한 후에 m도 동일하게 로직을 수행해 주면 된다.
8. 최종적으로 ans에 저장된 값을 출력해 준다.

 

참고 사항

• 0이하의 수는 최대한 작은 수 끼리 서로 묶어주는 것이 무조건 ans의 최대값에 도움이 된다.
• 1이상의 수는 최대한 큰 수 끼리 서로 묶어주는 것(1제외)이 무조건 ans의 최대값이 도움이 된다.

 

정답 코드

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

int n, ans;
priority_queue<int> p;
priority_queue<int, vector<int>, greater<int>> m;

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int num; cin >> num;
		if (num <= 0) m.push(num);
		else p.push(num);
	}

	while (!p.empty()) {
		int num = p.top(); p.pop();
		if (!p.empty()) {
			int tied = num * p.top();
			if (tied > num + p.top()) {
				ans += tied;
				p.pop();
				continue;
			}
		}
		ans += num;
	}

	while (!m.empty()) {
		int num = m.top(); m.pop();
		if (!m.empty()) {
			int tied = num * m.top();
			if (tied > num + m.top()) {
				ans += tied;
				m.pop();
				continue;
			}
		}
		ans += num;
	}
	cout << ans;
}