Beakjoon] 수 묶기 (백준 1744 코테) - 그리디

---

🅰️문제주소 : https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

🚩문제 

 

 

🪡풀이 

 - 최댓값을 구하기 위해 공식을 잘 살펴보면 양/음 수끼리 절댓값이 큰 수의 곱을 묶어줘야 하며
 0은 절대로 곱해져서는 안되며 양수 1은 곱해 봤자 이므로 더해줘야 한다.
 - 위의 분석으로 숫자는 4개의 타입을 가진다 (0, 1, 1을 제외한 양수, 음수)
 - 1을 제외한 양수와 음수는 우선순위 큐로 나눠서 정렬시키고 남은 수가 1개 이하가 될 때까지 곱을 묶어준다
 - 마지막 음수에 -1이 남는경우 0이 있는지 체크하여 0과 곱해줘서 없애준다
 - 정렬시 음수는 작은 순부터 정렬시켜야 한다. (절댓값이 커야 하므로)

         + 이 악마같은 예제는 음수가 하나뿐이라 이 정렬을 잘못해도 모든 예제를 통과해 버린다.

 

☕코드는 아래 숨김

#include <iostream>
#include <queue>
#include <vector>

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

	int N;
	std::cin >> N;

	std::priority_queue<int, std::vector<int>, std::less<int>> plus;
	std::priority_queue<int, std::vector<int>, std::greater<int>> minus;
	int zero_cnt = 0;
	int one_cnt = 0;

	for (int i = 0; i < N; ++i) {
		int temp;
		std::cin >> temp;
		if (temp > 1) {
			plus.push(temp);
		}
		else if (temp == 0)
			++zero_cnt;
		else if (temp == 1)
			++one_cnt;
		else {
			minus.push(temp);
		}
	}

	int result = one_cnt;

	while (plus.size() > 1) {
		int first = plus.top();
		plus.pop();
		int second = plus.top();
		plus.pop();
		result += first * second;
	}
	if (!plus.empty()) {
		result += plus.top();
	}

	while (minus.size() > 1) {
		int first = minus.top();
		minus.pop();
		int second = minus.top();
		minus.pop();
		result += first * second;
	}
	if (!minus.empty()) {
		if (zero_cnt > 0) {
			zero_cnt--;
		}
		else
			result += minus.top();		
	}

	std::cout << result;
	

	return 0;
}

 

💡알게 된 것 

 - 우선순위 큐의 사용 숙련도 상승
 - 그리디 알고리즘은 특정 스킬을 공식화해서 풀기보다는 문제를 정확히 이해하고 조건을 찾아낼 수 있어야 한다.

---