1744_수 묶기

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

1744번: 수 묶기

문제

  길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

  예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

  수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

  수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

  첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

  수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

예제 입력 1 복사

4

-1

2

1

3

예제 출력 1 복사

6

---

문제 접근

  1. 양수배열을 내림차순으로 정렬한다. / 음수배열은 오름차순으로 정렬한다.

  2. 0 이상의 양수일 경우 뒤에서 부터 묶고 0 미만의 음수일경우는 앞에서 묶는다.

 

  저는 이것을 구현하기 위해 일단 두 개의 벡터를 만들었습니다. 하나는 양수를 저장할 벡터배열 두번째는 음수와 0을 저장할 벡터배열 여기서 0을 저장하는 이유는 -3 * 0 과 같은 경우 때문에 이러한 범위를 두었습니다.

 

  다른 이들의 풀이를 참고하였을 때 아에 1을 예외로 주지 않고 1 자체를 카운트 해서 따로 더하는 경우의 풀이도 있었습니다. 제 생각에는 그 분의 풀이가 더 좋다고 생각합니다. 제 풀이 같은 경우 1을 예외처리를 함으로써 덧셈을 진행하는데 1자체를 따로 카운트 해버린다면 이렇게 따로 생각할 필요도 없으니 좋은거 같습니다.

 

/* 수 묶기 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, ans = 0;
vector<int> vecMinus;
vector<int> vecPlus;

bool compare(int a, int b) {
	return a > b;
}

int main(void) {
	cin >> n;
	for(int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if(temp <= 0) {
			vecMinus.push_back(temp);
		}
		else {
			vecPlus.push_back(temp);
		}
	}
	sort(vecPlus.begin(), vecPlus.end(), compare);
	sort(vecMinus.begin(), vecMinus.end());
	
	for(int i = 0; i < vecPlus.size(); i++) {
		if(i + 1 < vecPlus.size() && vecPlus[i] != 1 && vecPlus[i + 1] != 1) {
			ans += vecPlus[i] * vecPlus[i + 1];
			i++;
		}
		else {
			ans += vecPlus[i];
		}
	}
	for(int i = 0; i < vecMinus.size(); i++) {
		if(i + 1 < vecMinus.size()) {
			ans += vecMinus[i] * vecMinus[i + 1];
			i++;
		}
		else {
			ans += vecMinus[i];
		}
	}
	
	cout << ans << endl;
	return 0;
}