[백준] 1744번 수 묶기

문제: 1744번: 수 묶기

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더

using namespace std;

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

	int n;
	cin >> n;
	
	priority_queue<int, vector<int>, greater<int>> nums;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		nums.push(tmp);
	}

	int sum = 0;
	while (nums.size() >= 2) {
		bool flag = nums.size() % 2 == 0 ? true : false; // nums 의 요소 개수가 짝수인지 홀수인지 판단..
		int num1 = nums.top();
		nums.pop();
		int num2 = nums.top();
		nums.pop();

		if (num1 < 0 && num2 < 0) {
			sum += num1 * num2;
		}
		else if (num1 < 0 && num2==0) {
			sum += num1 * num2;
		}
		else if (num1 < 0 && num2 > 0) {
			// num1 단독으로 더하고 num2 는 다시 넣어
			sum += num1;
			nums.push(num2);
		}
		else if (num1 == 0 && num2 == 0) {
			sum += 0;
		}
		else if (num1 == 0 && num2 > 0) {
			sum += num2;
		}
		else if (num1 > 0 && num2 > 0) {
			if (num1 == 1 && num2 == 1)
				sum += 2;
			else if (num1 == 1 && num2 > 1) {
				sum += num1;
				nums.push(num2);
			}
			else {
				// 홀수일때, num1 만 먼저 더함
				if (flag == false) {
					sum += num1;
					nums.push(num2);
				}
				else {
					sum += num1 * num2;
				}
			}
		}
	}
	while (!nums.empty()) {
		sum += nums.top();
		nums.pop();
	}
	cout << sum << "\n";


	return 0;
}

 

그냥 수들을 정렬만 시켜놓으면 간단하게 해결되는 문제였다.

 

수를 정렬시키기 위해서 나는 최소힙을 이용했다.

 

그렇다면 이제 수가 가장 커지는 경우를 생각을 해봐야 한다.

1. 음수*음수=양수 이므로 최소힙에서 빼낸 두 값이 모두 음수라면 둘을 묶는다.

2. 차례로 음수, 0의 값이 뽑혔다면 음수는 없애버리는게 좋으므로 둘을 묶는다.

3. 차례로 음수, 양수의 값이 뽑혔다면 이 둘을 곱했을 때 좋은 점이 없으므로 둘을 묶지 않는다.

4. 차례로 0, 0의 값이 뽑혔다면 둘을 묶는다.

5. 차례로 0, 양수의 값이 뽑혔다면 이 둘을 곱했을 때 좋은 점이 없으므로 둘을 묶지 않는다.

6. 차례로 양수, 양수의 값이 뽑혔을 경우(세가지 경우로 나뉨)

• 1, 1이 뽑힌 경우: 둘을 묶는다.
• 1, 1보다 큰 양수가 뽑힌 경우: 1이랑 다른 양수랑 곱하면 1을 손해보게 되니까 둘을 묶지 않는다.
• 둘 다 1보다 큰 양수일 경우(두가지 경우로 나뉨)
  • 큐의 요소의 개수가 짝수였을 경우: 큐의 요소의 개수가 짝수라면 그냥 차례로 둘을 묶는다.
  • 큐의 요소의 개수가 홀수였을 경우: 두 수를 뽑기 전 큐의 요소가 홀수개였다면, 이 둘을 묶지 않는다. 둘을 곱했을 때 수가 가장 크도록 해야하는데 이게 가장 크도록 하려면 맨 뒤에 요소 2개씩 묶어야 함. 짝수일때는 어차피 짝이 맞으니까 상관 안 했는데 홀수일 경우는 앞에서부터 2개씩 묶으면 맨 마지막에 가장 큰 수가 남으므로 손해. 즉, 뒤부터 두개씩 짝을 묶는 것처럼 하기 위해서 맨 처음에 뺀 거는 따로 더해주고 다음부터 다시 2개씩 묶음..

 

음.. 어렵지는 않았는데 뽑힌 수가 둘 다 1인 경우를 잘 생각하지 못해서 처음에 틀렸다. 그래도 빨리 풀어서 기분 좋았다. ^0^