[백준 알고리즘] 1744번 - 수 묶기 (그리디 알고리즘)

1. 문제 및 예시 실행결과

 

 그리디와 정렬을 사용하는 문제이다. 문제의 핵심만을 파악하면 구현은 어렵지 않은 문제이지만, 핵심을 파악하고 알고리즘을 정의하는 과정이 조금 어려웠다.

 

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

1744번: 수 묶기

---

---

 수열에서 두 수를 묶어 최대한 큰 수를 만드는 과정은 그렇게 어렵지 않다. 정렬한 후 뒤에서부터 두개의 수를 묶어 곱하면 된다. 가장 큰 수 두개를 곱하는 것이 가장 큰 수를 만드는 방법이기 때문이다. 이 과정에서 조금 생각해야할 부분은 음수, 0, 1이다. 이 부분은 풀이 과정에서 자세히 설명하겠다. 다음은 예제 입출력이다.

---

---

2. 풀이과정

 

 일단 기둥이 되는 일번화를 하자면, 양수의 수열은 가장 큰 수 즉 뒤에서 부터 두개씩 곱해준 후 더해주면 된다. 중요한 점은 음수이다. 음수는 가장 큰 수끼리 곱하면 안된다. 다음과 같은 수열이 있다고 해보자.

---

-6 -5 -4 -2 -1

---

 이 음수 배열은 오름 차순으로 정렬되어있다. 그럼 일반화처럼 되에서 부터 두개씩 곱해 더하면 다음과 같은 해를 가지게 된다.

---

-6 + (-5 * -4) + ( -2 * -1)

---

 이렇게 하면 답은 16이다. 다시말해 최대의 합이 아니다. 그럼 어떻게 해야할까? 음수들은 가장작은 수들부터 두개씩 곱해 더해주어야 한다. 다음 결과를 보자.

---

(-6 * -5) + (-4 * -2) -1

---

 이런방식으로 계산하면 답은 37로 그 전 답보다 훨씬 큰 답이 나온다. 그럼 다음과 같은 알고리즘이 나온다.

---

1. 양수는 오름차순 정렬 후 뒤에서 부터 두개씩 곱해 더해준다.

2. 양수는 오름차순 정렬 후 앞에서 부터 두개씩 곱해 더해준다.

---

 이렇게만 하면 될까? 아쉽게도 아니다. 아직 '0'과 '1'을 처리해줘야 한다. 그렇다면 생각해보자 이 둘을 어떻게 해줘야 할까?

 

 정수 '1'은 곱하는 것보다 더하는 가장 좋다. 어떤 수가 오더라도 1과 곱해지는 것보다는 더해지는 것이 가장 큰 수를 만드는 방버이다. 결국 1은 수열에 넣지 않고 1의 수를 파악한 후 그대로 더해주는 것이 좋다. 0은 어떻게 해야할까? 0은 음수를 없애주는 용도로 사용하면 된다. 위의 수열을 다시 보자.

---

(-6 * -5) + (-4 * -2) -1 + 0

---

 이런 상황이라면 0과 -1을 곱해주면 -1이 사라지므로 더 큰 수를 만들 수 있다. 그럼 다음과 같은 상황은 어떨까?

---

(-6 * -5) + (-4 * -2) + 0

---

 이상황 역시 그냥 0을 더해주면 되므로, 아무 의미가 없다. 결국 우리는 다음과 같은 알고리즘을 만들 수 있다.

---

1. 양수와 음수를 다른 배열에 저장하고 정렬한다.

2. 단 1은 배열에 넣지않고 갯수를 카운트 하여 답에 더해준다.

3. 0은 음수와 같은 배열에 넣어준다.

4. 양수배열은 뒤에서 부터 두개씩 묶어 곱하고 더한다. 남은 숫자는 그냥 더해준다.

5. 음수배열은 앞에서 부터 두개씩 묶어 곱하고 더한다. 남은 숫자는 그냥 더해주낟.

---

 다음과 같은 알고리즘으로 코드를 구현하면 된다. 다음은 소스 코드이다.

 

3. 소스 코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {

	int size;
	vector<int> numbers_pos;
	vector<int> numbers_min;
	int count_one = 0;
	bool dir = false;
	int ans = 0;

	cin >> size;

	for (int i = 0; i < size; i++) {
		int buff;
		cin >> buff;
		
		if (buff > 0) {
			if (buff == 1)
				count_one++;
			else
				numbers_pos.push_back(buff);
		}
			
		else
			numbers_min.push_back(buff);

	}

	sort(numbers_pos.begin(), numbers_pos.end());
	sort(numbers_min.begin(), numbers_min.end());

	if (!numbers_pos.empty()) {
		for (int i = numbers_pos.size() - 1; i >= 1; i -= 2) {
			ans += numbers_pos[i] * numbers_pos[i - 1];

			if (i == 1)
				dir = true;
		}

		if (!dir && !numbers_pos.empty())
			ans += numbers_pos[0];
	}
		
	dir = false;

	if (!numbers_min.empty()) {
		for (int i = 0; i < numbers_min.size() - 1; i += 2) {
			//cout << 1;
			ans += numbers_min[i] * numbers_min[i + 1];

			if (i == numbers_min.size() - 2)
				dir = true;
		}

		if (!dir && !numbers_min.empty())
			ans += numbers_min[numbers_min.size() - 1];
	}


	cout << ans + count_one;
	return 0;

}