[그리디 #4] BOJ 1744 - 수 묶기

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

1744번: 수 묶기

 

1차 시도

큰 수끼리 곱하면 된다고 막연하게 생각했다.

근데 예제를 보면 예외가 몇 개 포함되어 있다.

 

1. 1일 때는 곱하면 안된다.

2. 0일 때는 음수랑만 곱한다.

 

그런데 반례를 찾을 수 있었다.

 

5 -3 -2 -1 1 2 답: 8

출처: 맨 아래 블로그

 

큰 음수끼리 곱해야 가장 커진다는 점을 간과했다.

 

접근방법

그래서 전체적인 프로세스를 구상했다.

 

준비

1. 양수, 0, 음수를 각각의 vector에 저장한다.

2. 양수는 내림차순, 음수는 오름차순으로 정렬한다.

 

알고리즘

1. 양수는 큰 수끼리 2개씩 곱해서 더한다. (1은 각각 더함)

2. 음수는 작은수 끼리 2개씩 곱해서 더해나간다.

3. 음수와 0을 곱해서 없애버린다.

4. 남은 것들을 더한다.

 

뜻 밖의 오류

위 예제에서 오류가 발생했다. (out of range)

6 0 1 2 4 3 5

vector를 neg, zero, pos로 나누어서 저장했는데 위 사례의 경우, neg가 값이 없다.

 

따라서, for (k=0; k < neg.size(); k++)가 true가 나와 버린다. (정확한 이유는 모르겠음...)

 

그래서 해당 vector가 empty인지 검증하는 로직을 추가해줘야 한다.

 

 

 

---

코드

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

using namespace std;

int n;

vector<long long> pos;
vector<long long> zero;
vector<long long> neg;

int main() {
	long long tmp;
	long long sum = 0;
	int i = 0;
	int j = 0;
	int k = 0;

	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp > 0)
			pos.push_back(tmp);
		else if (tmp == 0)
			zero.push_back(tmp);
		else
			neg.push_back(tmp);
	}

	sort(pos.begin(), pos.end(), greater<>());
	sort(neg.begin(), neg.end());

	if (!pos.empty()) {
		// 양수끼리 다 곱합 (1이면 더함)
		for (i = 0; i < pos.size() - 1; i++) {
			long long a = pos[i];
			long long b = pos[i + 1];

			if (a == 1 || b == 1) {
				sum += (a);
			}
			else {
				sum += (a * b);
				i++;
			}
		}
	}

	if (!neg.empty()) {
		// 음수끼리 다 곱합
		for (k = 0; k < neg.size() - 1; k++) {
			//cout << (k < neg.size() - 1) << endl;
			//cout << "???" << endl;
			long long a = neg[k];
			long long b = neg[k + 1];

			sum += (a * b);
			k++;
		}
	}

	if (!neg.empty() && !zero.empty()) {
		// 남은 음수랑 0 곱합
		while (k < neg.size() && j < zero.size()) {
			k++;
			j++;
		}
	}

	// 남는거 다 더함
	if (!pos.empty()) {
		while (i < pos.size()) {
			sum += pos[i];
			i++;
		}
	}
	if (!neg.empty()) {
		while (k < neg.size()) {
			sum += neg[k];
			k++;
		}
	}
	
	cout << sum;
}

 

 

 

참고 블로그

https://bingorithm.tistory.com/3

"백준 1744번-수 묶기" 반례 모음

반례 감사합니다 ( _ _ )