n개의 정수로 이루어진 배열 arr[n]과 부분 수열의 크기를 정의하는 정수 k가 주어졌을 때, 최솟값과 최댓값을 제외한 크기 k의 모든 부분 수열(subsequence)의 곱을 구하는 것이 이 문제의 목표입니다.
문제 이해하기
예를 들어 원소 4개짜리 집합 {1, 2, 3, 4}와 k = 2가 주어졌다고 가정해 보겠습니다. 이때 만들어질 수 있는 부분 수열은 다음과 같습니다.
{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}
여기서 최댓값인 4와 최솟값인 1을 제외하면 남는 원소는 다음과 같습니다.
2, 3, 3, 3, 2
이들의 곱을 계산하면 다음과 같습니다.
2 × 3 × 3 × 3 × 2 = 108
같은 방식으로 문제를 해결하면 됩니다.
예시
입력: arr[] = {3, 4, 1, 7}, k = 3
출력: 144
설명: 부분 수열은 {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7}
최댓값 7과 최솟값 1을 제거하면 다음과 같습니다.
{3, 4}, {4}, {3}, {3, 4}
이들을 모두 곱하면 다음과 같습니다.
3 × 4 × 4 × 3 = 144
입력: arr[] = {1, 2, 3, 4}, k = 3
출력: 36문제 해결 접근 방법
이 문제는 여러 가지 방법으로 풀 수 있습니다. 첫 번째 방법은 가능한 모든 부분 수열을 하나씩 생성한 뒤, 각 부분 수열에서 최댓값과 최솟값을 제외한 나머지 원소들의 곱을 계산하는 것입니다. 이 방법은 구현이 쉽지만 시간 복잡도가 매우 높아 비효율적입니다.
훨씬 더 효율적인 방법도 있습니다. 이 방법에서는 부분 수열을 직접 생성하지 않고, 먼저 배열 전체를 정렬한 뒤 각 원소가 곱셈에 기여하는 횟수를 하나씩 세어 나갑니다.
정렬된 배열에서 i번째 원소는 총 C(n−1, k−1)개의 부분 수열에 등장할 수 있으며, 그중 C(i, k−1)번은 해당 부분 수열의 최댓값으로, C(n−i−1, k−1)번은 최솟값으로 등장하게 됩니다.
따라서 i번째 원소가 실제 곱셈에 기여하는 횟수는 다음과 같이 정리할 수 있으며, 이것이 모든 부분 수열을 일일이 생성하는 방식보다 훨씬 효율적인 이유입니다.
C(n−1, k−1) − C(i, k−1) − C(n−i−1, k−1)
이제 각 원소 arr[i]에 대해 지수 x를 구해야 하는데, 이 지숫값이 매우 커질 수 있어 직접 계산하기 어려울 수 있습니다. 이럴 때 페르마의 소정리(Fermat's Little Theorem)를 활용하면 효과적으로 처리할 수 있습니다.
참고 − 결과값이 매우 커질 수 있으므로, 답은 109+7로 나눈 나머지(mod) 형태로 출력합니다.
알고리즘
시작
1단계 → 조합(combination)을 계산하는 함수 선언
void pairs(int a, int b)
int i, j 선언
i = 0부터 i <= a까지 반복
j = 0부터 j <= min(i, b)까지 반복
IF (j == 0 || j == i)
c[i][j] = 1로 설정
ELSE
c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val로 설정
2단계 → 거듭제곱 함수 선언
LL power(LL x, unsigned LL y)
unsigned LL temp = 1로 선언
x = x % val 설정
y > 0인 동안 반복
IF (y & 1)
temp = (temp * x) % val 설정
y = y >> 1 설정
x = (x * x) % val 설정
temp % val 반환
3단계 → 모든 부분 수열의 곱을 계산하는 함수 선언
unsigned LL product(LL arr[], int size, int k)
unsigned LL temp = 1로 선언 및 초기화
sort(arr, arr + size)를 호출해 배열 정렬
LL pow = c[size - 1][k - 1]로 선언 및 초기화
i = 0부터 i < size까지 반복
LL pow_l = c[i][k - 1] 선언
LL pow_f = c[size - i - 1][k - 1] 선언
LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val 선언
unsigned LL mul = power(arr[i], pow_e) % val 선언
temp = ((temp % val) * (mul % val)) % val 설정
temp % val 반환
4단계 → main()에서
pairs(100, 100) 호출
LL arr[] = { 3, 4, 1, 7 } 선언
size를 sizeof(arr) / sizeof arr[0]로 계산
int k = 3 선언
unsigned LL temp = product(arr, size, k) 선언
temp 출력
종료예제 코드
#include <bits/stdc++.h>
using namespace std;
#define val 1000000007
#define LL long long
#define max 101
LL c[max - 1][max - 1];
LL power(LL x, unsigned LL y) {
unsigned LL temp = 1;
x = x % val;
while (y > 0) {
if (y & 1) {
temp = (temp * x) % val;
}
y = y >> 1;
x = (x * x) % val;
}
return temp % val;
}
void pairs(int a, int b) {
int i, j;
for (i = 0; i <= a; i++) {
for (j = 0; j <= min(i, b); j++) {
if (j == 0 || j == i)
c[i][j] = 1;
else
c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val;
}
}
}
// 모든 부분 수열의 곱을 계산하는 함수
unsigned LL product(LL arr[], int size, int k) {
unsigned LL temp = 1;
// 배열 정렬
sort(arr, arr + size);
LL pow = c[size - 1][k - 1];
for (int i = 0; i < size; i++) {
LL pow_l = c[i][k - 1];
LL pow_f = c[size - i - 1][k - 1];
LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val;
unsigned LL mul = power(arr[i], pow_e) % val;
temp = ((temp % val) * (mul % val)) % val;
}
return temp % val;
}
int main() {
// 모든 조합 미리 계산
pairs(100, 100);
LL arr[] = { 3, 4, 1, 7 };
int size = sizeof(arr) / sizeof arr[0];
int k = 3;
unsigned LL temp = product(arr, size, k);
cout << "최솟값과 최댓값을 제외한 크기 k의 모든 부분 수열의 곱 : " << temp << endl;
return 0;
}출력
최솟값과 최댓값을 제외한 크기 k의 모든 부분 수열의 곱 : 144