[백준문제풀이] 1744 수 묶기

 

풀이일시 : 2020-10-16

​

 

문제 :

길이가 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보다 작거나 같은 정수이다.

ex)

4

-1

2

1

3

​

​

출력 :

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

ex)

6

​

​

풀이 :

수열이 주어졌을 때 괄호로 묶게되면 두 수가 곱해지고 이를 실행했을 때 최대가 되게하는 방법을 찾는 문제이다.

최대가 되려면.

​

최대한 큰 수끼리 묶는다.-> 음수x음수 / 양수x양수

음수는 0과는 묶되 양수랑은 묶지 않는다.

위와같은 규칙을 따라주면 될 것이다.

​

1. 12345가 주어졌을때 큰수끼리 묶으려면

1+(2x3)+(4x5)가 되어야 할 것이고, 이는 내림차순인 54321로 재정렬 후 앞에서부터 묶어주면 될 것이다.

​

2. -1 -2 -3 -4 -5가 주어졌을때 큰수끼리 묶으려면

(-5x-4)+(-3x-2)+-1 이 되어야 할 것이고 이는 오름차순인 -5-4-3-2-1로 재정렬 후 앞에서부터 묶어주면 될것.

​

3. -5 -4 -3 0 1 2 3 이 섞여있다면 어떻게 정렬해줘야될까

-5 -4 -3 0 3 2 1 로 정렬해주구 음수~0까지 연산해주고 양수끼리 연산해 주는 것이 최대값을 도출할 수 있는 방법일 것이다.

​

코드로 옮겨보자

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> v;

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

int main() {
	int N, s;
	int result = 0;
	int twice = 0;
	int now;
	int sortnum=-1;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s;
		v.push_back(s);
	}

	sort(v.begin(), v.end()); //sort로 작은순부터 정렬한다.
	//2 3 4 들어갔을때 2*3 + 4가 안되고 2+ 3*4 가 되게하는방법은? 여기서마힘

	//vector를 재정렬하기
	// -5 -4 -3 -2 -1 0 1 2 3 4 5 라면
	// -5 -4 -3 -2 -1 0 5 4 3 2 1 로

	for (int i = 0; i < v.size(); i++) {
		if (v[i] > 0) {
			sortnum = i;
			break;
		}
	}
	if (sortnum >= 0) {
		sort(v.begin() + sortnum, v.end(),compare);
	}

	while(!v.empty()) {
		int i = 0;
		if (twice == 0) { //두번 건너뛰었을때
			if (v[i] <= 0) { //현재 원소가 음수거나 0이면
				now = v[i]; //now에 값을 옮긴다
				v.erase(v.begin()); //vector원소 지운다. 다음원소는 v[i]가 될것이다.
				if (!v.empty()) { //다음이 비지 않았으면
					if (v[i] <= 0) { //다음 원소가 음수이면
						result += now * v[i];
						twice = 1; // 곱했으니깐 뛰어넘는다는 표시
					}
					else if (v[i] > 0) { //다음원소가 양수이면
						result += now;
						twice = 0;
					}
				}
				else { //다음이 비었으면 지금 하나만 더한다
					result += now;
				}
			}

			else if (v[i] > 0) { //현재 원소가 양수이면
				now = v[i];
				v.erase(v.begin()); //다음원소가 v[i]가 될 것이다.
				if (!v.empty()) { //다음이 비지 않았으면
					if (v[i] <= 1) { //1이하면 그거만 더한다
						result += now;
						twice = 0;
					}
					else if (v[i] > 1) { //2이상의 양수이면 양수끼리 곱한다.
						result += now * v[i];
						twice = 1;
					}
				}
				else { //다음원소가 없다면 하나만 더한다
					result += now;
				}
			}
		}

		else if (twice == 1) {
			twice = 0;
			v.erase(v.begin());
		}

	}
	cout << result << endl;
	return 0;
} 

 

추가자료 : vector container

dbstndi6316.tistory.com/25

[개념정리] vector container

 

추가자료 : sort()

dbstndi6316.tistory.com/22

[개념정리] STL라이브러리 - sort()2