문제 소개
이 글에서는 주어진 연산들을 수행한 후 배열에서 얻을 수 있는 최대 곱을 찾는 프로그램을 다룹니다.
크기가 N인 배열이 주어지며, 우리는 정확히 N-1번의 연산을 수행해야 합니다. 사용할 수 있는 연산은 다음 두 가지입니다.
- 연산 1: a[j]를 a[i] × a[j]로 바꾸고, a[i]를 배열에서 제거
- 연산 2: a[i]를 그대로 제거 (단, 전체 과정에서 한 번만 사용 가능)
목표는 이 연산들을 적절히 조합하여 마지막에 남는 값이 최대가 되도록 만드는 것입니다.
접근 방법
최대 곱을 얻으려면 배열 원소의 부호에 따라 다음과 같이 처리해야 합니다.
- 0 처리: 0은 어떤 값과 곱해도 결과를 키우지 못하므로 항상 제거 대상입니다.
- 음수 처리: 음수가 짝수 개라면 서로 곱해 양수로 만들 수 있지만, 홀수 개라면 절댓값이 가장 작은 음수 하나를 제거해야 손실을 최소화할 수 있습니다.
- 특수 경우: 배열 전체가 0이거나, 0과 음수 하나만 남는 경우 곱은 항상 0이 되므로 나머지 원소들을 순서대로 하나로 합칩니다.
연산 출력 형식은 아래와 같습니다.
1 i j: a[j]를 a[i] × a[j]로 갱신한 뒤 a[i]를 제거2 i: a[i]를 그냥 제거
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 연산 과정을 출력하는 함수
void MaximumProduct(int a[], int n) {
int cntneg = 0; // 음수 개수
int cntzero = 0; // 0의 개수
int used[n] = { 0 }; // 제거 대상 표시 배열
int pos = -1; // 절댓값이 가장 작은 음수의 위치
for (int i = 0; i < n; ++i) {
if (a[i] == 0) {
used[i] = 1;
cntzero++;
}
if (a[i] < 0) {
cntneg++;
if (pos == -1 || abs(a[pos]) > abs(a[i]))
pos = i;
}
}
// 음수가 홀수 개면 절댓값이 가장 작은 음수를 제거 대상으로 지정
if (cntneg % 2 == 1)
used[pos] = 1;
// 모든 원소가 0이거나, 0과 음수 하나만 있는 특수 경우
if (cntzero == n || (cntzero == n - 1 && cntneg == 1)) {
for (int i = 0; i < n - 1; ++i)
cout << 1 << " " << i + 1 << " " << i + 2 << endl;
return;
}
// 제거 대상 원소들을 하나로 합친 뒤 삭제
int lst = -1;
for (int i = 0; i < n; ++i) {
if (used[i]) {
if (lst != -1)
cout << 1 << " " << lst + 1 << " " << i + 1 << endl;
lst = i;
}
}
if (lst != -1)
cout << 2 << " " << lst + 1 << endl;
// 남은 원소들을 왼쪽부터 차례로 곱해 하나로 합침
lst = -1;
for (int i = 0; i < n; ++i) {
if (!used[i]) {
if (lst != -1)
cout << 1 << " " << lst + 1 << " " << i + 1 << endl;
lst = i;
}
}
}
int main() {
int a[] = { 5, -2, 0, 1, -3 };
int n = sizeof(a) / sizeof(a[0]);
MaximumProduct(a, n);
return 0;
}
실행 결과
2 3 1 1 2 1 2 4 1 4 5
결과 해석
입력 배열이 {5, -2, 0, 1, -3}일 때 위 출력은 다음 과정을 의미합니다.
2 3→ 위치 3의 값(0)을 먼저 제거합니다.1 1 2→ 위치 1의 값(5)을 위치 2의 값(-2)과 곱해 -10으로 만든 뒤, 위치 1의 값을 제거합니다.1 2 4→ 위치 2의 값(-10)을 위치 4의 값(1)과 곱해 -10으로 만든 뒤, 위치 2의 값을 제거합니다.1 4 5→ 위치 4의 값(-10)을 위치 5의 값(-3)과 곱해 30으로 만든 뒤, 위치 4의 값을 제거합니다.
최종적으로 배열에 남는 값은 30이며, 이것이 해당 배열에서 얻을 수 있는 최대 곱입니다.
복잡도 분석
- 시간 복잡도: O(N) — 배열을 몇 번의 선형 탐색만으로 처리합니다.
- 공간 복잡도: O(N) — 각 원소의 제거 여부를 저장하는 보조 배열이 필요합니다.
마무리
이 문제의 핵심은 0과 짝을 맞추지 못하는 음수를 얼마나 효율적으로 걸러내느냐에 있습니다. 음수와 0의 개수만 미리 파악하면 한 번의 순회로 최적의 연산 순서를 결정할 수 있으므로, 그리디 관점에서 O(N)에 해결되는 전형적인 유형이라 할 수 있습니다.