문제 설명
당신은 여러 개의 정수를 주어지는 동안, 이 정수들을 적절히 묶어서 하나의 최댓값을 만들어야 합니다. 이 때
정수들은 다음의 규칙을 따릅니다:
- 정수는 음수와 양수를 포함할 수 있으며, 0도 존재합니다.
- 음수와 음수를 곱하면 양수가 되고, 이를 통해 더 큰 수를 만들 수 있습니다.
- 양수는 1보다 큰 경우에만 다른 수와 곱해져야, 그 결과가 더 큰 수를 만듭니다. 1은 더하기에 사용합니다.
- 0은 최댓값에 영향을 미치지 않지만, 음수와 곱할 수 있습니다.
예를 들어, 당신에게 주어진 정수가 {1, 2, 0, -1, -2}라고 가정할 때, 최댓값을 만들기 위해서는
(2 * 1) + (0) + ((-1) * (-2)) = 2 + 0 + 2 = 4 가 됩니다.
입력
첫 번째 줄에 정수 N (1 ≤ N ≤ 100,000)이 주어지고,
두 번째 줄에는 N개의 정수 arr[i] (-1,000 ≤ arr[i] ≤ 1,000)이 주어집니다.
출력
정수들의 최댓값을 한 줄에 출력합니다.
문제 해결 과정
1단계: 입력 읽기
입력된 정수를 읽어 컴퓨터가 이해할 수 있는 형태로 변환합니다. C++에서는
vector를 사용하여 정수들을 저장합니다.
전체 값들을 하나의 리스트로 저장하여 처리합니다.
2단계: 정수 분리
먼저 양수, 음수 및 0으로 정수들을 분리합니다. 이를 통해 다양한 경우를
효율적으로 처리할 수 있습니다. 음수들을 묶어 곱하여 양수를 만들고,
양수는 최댓값이 되도록 조합하는 것이 목표입니다.
3단계: 양수 처리
양수 리스트를 정렬하여 마지막에 있는 큰 값들을 먼저 곱합니다. 1보다 큰 값만
조합할 수 있으므로 1과 함께 묶는 것이 좋습니다.
4단계: 음수 처리
음수를 처리는 두 개씩 묶어서 곱해 최댓값을 만드는 방법으로 진행합니다. 예를 들어,
두 개의 음수를 곱하면 양수가 되므로 이들을 조합해야 합니다.
5단계: 결과 계산 및 출력
결국 모든 조합을 통해 얻은 최댓값을 저장하고, 이를 출력합니다.
이 과정은 아래의 C++ 코드를 통해 쉽게 구현할 수 있습니다.
코드 예시
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector arr(N);
vector positive;
vector negative;
for (int i = 0; i < N; i++) {
cin >> arr[i];
if (arr[i] > 0) positive.push_back(arr[i]);
else if (arr[i] < 0) negative.push_back(arr[i]);
}
sort(positive.rbegin(), positive.rend());
sort(negative.begin(), negative.end());
long long result = 0;
for (int i = 0; i < positive.size(); i += 2) {
if (i + 1 < positive.size()) {
result += positive[i] * positive[i + 1];
} else {
result += positive[i];
}
}
for (int i = 0; i < negative.size(); i += 2) {
if (i + 1 < negative.size()) {
result += negative[i] * negative[i + 1];
}
}
cout << result << endl;
return 0;
}
결론
본 문제는 주어진 정수들을 통해 최댓값을 만들어내는 중요한 알고리즘 문제입니다.
위의 접근 방식은 주어진 문제를 효과적으로 해결할 수 있도록 도와줍니다.
기본적으로 정수를 분류하고 그에 따라 적절한 수학적 조작을 통해
결과를 도출하는 것이 핵심입니다. C++의 STL을 활용한 코드 작성법도 익혀
다른 문제에 적용할 수 있습니다.