그리디 알고리즘 - 수를 묶어 최댓값 만들기

이번에는 두 수를 묶어 최댓값을 만드는 문제를 풀어보고자 한다. 이전에 풀었던 카드 정렬하기와 비슷한 문제이다.

 

<문제>

백준 - 1744: 수를 묶어서 최댓값 만들기

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

1744번: 수 묶기

 

수열을 합을 구하기 전에 먼저 수열 안에 있는 임의의 두 수를 묶어 곱한 후 그 합을 최대로 만드는 프로그램이다. 

 

예)

입력     출력

6           27
0
1
2
4
3
5

<문제 해결>

자료구조나 알고리즘 라이브러리를 이용해 풀어야 하는 문제이며 여러가지 경우를 고려해야 한다.

 

1. 위치에 따라 적절히 숫자들을 묶어 주기 위해서 오름차순으로 정렬한다. 우선순위 큐를 이용해서 정렬하거나 벡터에 sort 함수를 이용해 정렬해도 된다. (필자는 우선순위 큐를 이용함)

 

2. 연속적이지 않은 두 개의 숫자를 묶어가면서 최댓값을 만들어야 하기 때문에 두 개의 숫자를 묶는 여부를 크게 3가지 유형으로 나누어야 한다.

 

    2-1. 두 숫자 중 첫 번째 숫자인 f가 0이거나 1인 경우:

    → f가 0일 때, 두 개의 수를 묶어 곱하게 되면 그 값이 항상 0이되므로 최댓값을 만들 수 없다. 

    → f가 1일 때, 두 개의 수를 묶어 곱하게 되면 그 값이 항상 두 숫자 중 두 번째 숫자이되므로

        최댓값을 만들 수 없다. 

 

    2-2. 두 숫자 중 첫 번째 숫자인 f가 1보다 큰 경우:

    → 우선순위 큐 안에 담긴 수의 개수가 짝수 개일 때, 두 개의 수를 묶어 곱한 후 합해야지 최댓값을 만들 수 있다.

    → 우선순위 큐 안에 담긴 수의 개수가 홀수 개일 때, 큐 안에 담긴 수들 중 가장 작은 수 한 개는 최종 sum에

        합하고, 나머지 수들은 두 개씩 묶어 곱한 후 합해야지 최댓값을 만들 수 있다.

 

    2-3. 두 숫자 중 첫 번째 숫자인 f가 0보다 작은 경우:

    → 큐에 더이상 수가 존재하지 않을때, f만 최종 sum에 합한다.

    → 두 숫자 중 두 번째 숫자인 s가 0보다 작거나 같은 경우, f와 곱한 후 최종 sum에 합해준다.

    → 두 숫자 중 두 번째 숫자인 s가 0보다 큰 경우, f만 최종 sum에 합해준다.

 

3. 우선순위 큐에 담긴 수가 하나일 때 시간 복잡도를 고려해야 한다.

 

Corner case 정리)

1. 우선순위 큐에 담긴 수가 한 개이고, 그 수가 음수이거나 양수일 때 시간 초과가 되지 않도록 해야한다. 

2. f 값에 따른 조건을 모두 고려해줘야 한다.

 

<슈도 코드>

n = 수의 개수
num = 입력할 수
f = 두 숫자 중 첫 번째 숫자
s = 두 숫자 중 두 번째 숫자
sum = 최댓값을 만들기 위한 수들의 합

	cin >> n;

	priority_queue <int, vector<int>, greater<int>> pq;

	for (int i = 0; i < n; i++) { 
		cin >> num;
		pq.push(num);
	}
	
	while (!pq.empty()) {

		f = pq.top();

		if (f가 0이거나 1일 때) { 
			pq.pop();
			sum = sum + f;
		}

		else if(f가 1보다 클 때){ 
			if (pq.size()가 홀수일 때) {
				pq.pop();
				sum = sum + f;
			}
			else { // pq.size()가 짝수일 때
				pq.pop();
				s = pq.top();
				pq.pop();
				sum = sum + f * s;
			}
		}

		else { // f가 0보다 작을 때
			pq.pop();
			if (pq.size()가 0개일 때) {  
				sum = sum + f;
			}
			else {
				if (pq.top()이 0보다 작거나 같을 때) {
					s = pq.top();
					pq.pop();
					sum = sum + f * s;
				}
				else { // pq.top()이 0보다 클 때
					sum = sum + f;
				}
			
			}
			
		}
		
	}

	cout << sum;

 

<전체 코드>

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, num;
	int f = 0, s = 0;
	int sum = 0;

	cin >> n;

	priority_queue <int, vector<int>, greater<int>> pq;

	for (int i = 0; i < n; i++) {
		cin >> num;
		pq.push(num);
	}
	
	while (!pq.empty()) {

		f = pq.top();

		if ((f == 0) || (f == 1)) {
			pq.pop();
			sum = sum + f;
		}

		else if(f > 1){ 
			if (pq.size() % 2 == 1) {
				pq.pop();
				sum = sum + f;
			}
			else { // pq.size() % 2 == 0
				pq.pop();
				s = pq.top();
				pq.pop();
				sum = sum + f * s;
			}
		}

		else { // f < 0
			pq.pop();
			if (pq.size() == 0) {  // pq.top()이 존재하지 않는 경우
				sum = sum + f;
			}
			else {
				if (pq.top() <= 0) {
					s = pq.top();
					pq.pop();
					sum = sum + f * s;
				}
				else { // pq.top() > 0
					sum = sum + f;
				}
			
			}
			
		}
		
	}

	cout << sum;
	
}