네 개의 정수 배열이 주어졌을 때, 각 배열에서 하나씩 원소를 선택해 만든 네 원소 조합(쿼드러플렛) 중 그 합이 주어진 값(Sum)과 일치하는 경우가 몇 가지인지 구하는 것이 이 문제의 목표입니다. 단, 선택된 네 원소는 반드시 서로 다른 배열에 속해 있어야 합니다.
가장 직관적인 풀이 방법은 4중 반복문으로 가능한 모든 조합을 탐색하면서 A[i] + B[j] + C[k] + D[l] == sum 조건을 확인하는 것입니다. 조건이 참이면 카운트를 1씩 증가시키면 됩니다.
예제로 이해하기
입력 −
A[]={ 1,3,1 }, B[]={ 2,4,5 }, C[]={ 1,1,2 }, D[]={ 4,4,0 }, Sum=5출력 − 주어진 합을 만족하는 쿼드러플렛의 개수: 2
설명 −
조건을 만족하는 2개의 쿼드러플렛:
(A[0],B[0],C[2],D[2]) → (1,2,2,0), 합 = 5
(A[2],B[0],C[2],D[2]) → (1,2,2,0), 합 = 5
입력 −
A[]={ 1,1,1 }, B[]={ 1,1,1 }, C[]={ 1,1,1 }, D[]={ 1,1,1 }, Sum=3출력 − 주어진 합을 만족하는 쿼드러플렛의 개수: 0
설명 − 어떤 조합을 선택하더라도 네 원소의 합은 항상 4로, 목표 값 3보다 크기 때문에 조건을 만족하는 경우가 없습니다.
알고리즘 접근 방법
- 정수 배열 first[], second[], third[], fourth[]를 임의의 값으로 초기화합니다.
- 각 배열의 길이를 저장할 변수 first_size, second_size, third_size, fourth_size를 선언합니다.
- 목표 합을 저장할 변수 sum을 준비합니다.
- quadruplets() 함수는 네 개의 배열과 각 배열의 길이, 그리고 sum을 매개변수로 받아 조건을 만족하는 쿼드러플렛의 개수를 반환합니다.
- 4중 FOR 루프로 각 배열을 순회합니다. 바깥쪽부터 순서대로 first[](i), second[](j), third[](k), fourth[](l)의 인덱스를 사용하며, 범위는 각각 0 ≤ i < first_size, 0 ≤ j < second_size, 0 ≤ k < third_size, 0 ≤ l < fourth_size 입니다.
- first[i] + second[j] + third[k] + fourth[l] == sum 인지 비교하고, 참이면 count를 증가시킵니다.
- 모든 루프가 종료되면 count에는 조건을 만족하는 쿼드러플렛의 개수가 저장됩니다.
- count를 결과값으로 반환합니다.
이 방법의 시간 복잡도는 O(n⁴)입니다. 배열의 크기가 커지면 탐색 시간이 급격히 증가하므로, 실제 환경에서는 두 배열씩 묶어 부분합을 해시 맵에 저장한 뒤 나머지 두 배열의 부분합과 짝을 찾는 방식(O(n²))으로 최적화할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int quadruplets(int first[], int second[], int third[], int fourth[], int first_size, int second_size, int third_size, int fourth_size, int sum){
int count = 0;
for (int i = 0; i < first_size; i++){
for (int j = 0; j < second_size; j++){
for (int k = 0; k < third_size; k++){
for (int l = 0; l < fourth_size; l++){
if (first[i] + second[j] + third[k] + fourth[l] == sum){
count++;
}
}
}
}
}
return count;
}
int main(){
int first[] = { 7, -8 };
int second[] = { 7, -2 };
int third[] = { 4, -2 };
int fourth[] = { 3, -4 };
int first_size = sizeof(first) / sizeof(first[0]);
int second_size = sizeof(second) / sizeof(second[0]);
int third_size = sizeof(third) / sizeof(third[0]);
int fourth_size = sizeof(fourth) / sizeof(fourth[0]);
int sum = 0;
cout<<"주어진 합을 만족하는 쿼드러플렛의 개수: "<<quadruplets(first, second, third, fourth, first_size, second_size, third_size, fourth_size, sum);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
주어진 합을 만족하는 쿼드러플렛의 개수: 1
이 예제에서 합이 0이 되는 유일한 조합은 (-8, 7, -2, 3)이므로 결과는 1이 됩니다.