문제 개요
이 문제에서는 3개의 배열 X, Y, Z가 주어지며, 각 배열에서 하나씩 요소를 선택해 만들 수 있는 특수 삼중항(special triplet)들의 값의 총합을 구하는 프로그램을 작성해야 합니다.
특수 삼중항은 다음 조건을 만족하는 삼중항입니다.
(a, b, c)에 대해 a ≤ b 이고 b ≥ c, 즉 삼중항의 가운데 요소가 나머지 두 요소보다 크거나 같아야 합니다.
삼중항의 값은 다음 공식으로 계산됩니다.
f(a, b, c) = (a+b) * (b+c)
즉, 주어진 세 배열에서 각각 하나의 요소를 가져와 위 조건을 만족하는 조합을 찾고, 그 값들을 모두 더하는 것이 목표입니다.
예제로 문제 이해하기
입력 −
X[] = {5, 9, 4} ; Y[] = {8, 6} ; Z[] = {7, 1}출력 − 747
설명 − 가능한 모든 특수 삼중항의 값을 계산해 보면 다음과 같습니다.
(5, 8, 7) : 값 = (5+8) * (8+7) = 195 (5, 8, 1) : 값 = (5+8) * (8+1) = 117 (4, 8, 7) : 값 = (4+8) * (8+7) = 180 (4, 8, 1) : 값 = (4+8) * (8+1) = 108 (5, 6, 1) : 값 = (5+6) * (6+1) = 77 (4, 6, 1) : 값 = (4+6) * (6+1) = 70 특수 삼중항의 합 = 747
방법 1: 완전 탐색(Brute Force)
가장 단순한 해결 방법은 세 배열로부터 만들 수 있는 모든 삼중항을 생성하는 것입니다. 각 조합이 특수 삼중항 조건을 만족하는 경우에만 위 공식으로 값을 계산해 합계 변수에 누적하고, 최종 합을 반환합니다. 이 방식은 세 개의 중첩 반복문을 사용하므로 시간 복잡도가 O(N³)으로, 입력 크기가 커지면 비효율적입니다.
예제 코드
#include <iostream>
using namespace std;
int findSpecialTripletSum(int X[], int Y[], int Z[], int sizeX, int sizeY, int sizeZ) {
int sum = 0;
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
for (int k = 0; k < sizeZ; k++) {
if (X[i] <= Y[j] && Z[k] <= Y[j])
sum = sum + (X[i] + Y[j]) * (Y[j] + Z[k]);
}
}
}
return sum;
}
int main() {
int X[] = {5, 9, 4};
int Y[] = {8, 6};
int Z[] = {7, 1};
int sizeX = sizeof(X) / sizeof(X[0]);
int sizeY = sizeof(Y) / sizeof(Y[0]);
int sizeZ = sizeof(Z) / sizeof(Z[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(X, Y, Z, sizeX, sizeY, sizeZ);
}출력
Sum of special triplets = 747
방법 2: 정렬과 누적 합을 활용한 효율적인 접근
더 효율적인 방법은 배열 X와 Z를 먼저 오름차순으로 정렬한 뒤, 배열 Y의 각 요소에 대해 특수 삼중항 조건을 만족하는 요소들을 이분 탐색으로 빠르게 찾는 것입니다.
배열 Y의 인덱스 i에 있는 요소를 Y[i]라고 할 때, 배열 X의 요소 {x1, x2}와 배열 Z의 요소 {z1, z2}가 모두 Y[i] 이하라고 가정하면, 가능한 모든 삼중항 값의 합은 다음과 같이 전개할 수 있습니다.
S = (x1+Y[i])(Y[i]+z1) + (x1+Y[i])(Y[i]+z2) + (x2+Y[i])(Y[i]+z1) + (x2+Y[i])(Y[i]+z2) S = (x1+Y[i])(2Y[i]+z1+z2) + (x2+Y[i])(2Y[i]+z1+z2) S = (2Y[i] + x1 + x2)(2Y[i] + z1 + z2)
여기서 다음과 같이 정의하겠습니다.
- N = 배열 X에서 Y[i] 이하인 요소의 개수
- M = 배열 Z에서 Y[i] 이하인 요소의 개수
- Sx = 배열 X에서 Y[i] 이하인 요소들의 합
- Sz = 배열 Z에서 Y[i] 이하인 요소들의 합
그러면 합 S는 아래처럼 간단한 곱셈 형태로 단순화됩니다.
S = (N*Y[i] + Sx) * (M*Y[i] + Sz)
정렬된 배열에서 upper_bound를 사용하면 Y[i] 이하인 요소의 개수와, 미리 계산해 둔 누적 합(prefix sum) 배열을 통해 그 합을 O(log N) 만에 구할 수 있습니다. 따라서 전체 시간 복잡도는 정렬 비용을 포함해 약 O(N log N) 수준으로, 완전 탐색 방식보다 훨씬 효율적입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int tripletSumCalc(int X[], int Y[], int Z[], int prefixSumA[], int prefixSumC[], int sizeA, int sizeB, int sizeC){
int totalSum = 0;
for (int i = 0; i < sizeB; i++) {
int currentElement = Y[i];
int n = upper_bound(X, X + sizeA, currentElement) - X;
int m = upper_bound(Z, Z + sizeC, currentElement) - Z;
if (n == 0 || m == 0)
continue;
totalSum += ((prefixSumA[n - 1] + (n * currentElement)) * (prefixSumC[m - 1] + (m * currentElement)));
}
return totalSum;
}
int* findPrefixSum(int* arr, int n) {
int* prefixSumArr = new int[n];
prefixSumArr[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];
return prefixSumArr;
}
int findSpecialTripletSum(int A[], int B[], int C[], int sizeA, int sizeB, int sizeC){
sort(A, A + sizeA);
sort(C, C + sizeC);
int* prefixSumA = findPrefixSum(A, sizeA);
int* prefixSumC = findPrefixSum(C, sizeC);
return tripletSumCalc(A, B, C, prefixSumA, prefixSumC, sizeA, sizeB, sizeC);
}
int main() {
int A[] = {5, 9, 4};
int B[] = {8, 6};
int C[] = {7, 1};
int sizeA = sizeof(A) / sizeof(A[0]);
int sizeB = sizeof(B) / sizeof(B[0]);
int sizeC = sizeof(C) / sizeof(C[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(A, B, C, sizeA, sizeB, sizeC);
}출력
Sum of special triplets = 747
마무리
완전 탐색 방식은 구현이 간단하지만 O(N³)의 시간 복잡도를 가지는 반면, 정렬과 누적 합, 이분 탐색을 결합한 최적화 기법은 동일한 결과를 훨씬 빠르게 얻을 수 있습니다. 입력 배열의 크기가 큰 실전 문제에서는 후자의 접근 방식을 사용하는 것이 바람직합니다.