이 문제에서는 요소의 개수를 나타내는 정수 n이 주어지며, 우리의 과제는 결합 법칙(associative operation)을 적용하여 n개의 요소를 곱할 수 있는 경우의 수를 세는 프로그램을 작성하는 것입니다.
결합 법칙(연관 연산)이란 숫자들을 어떤 순서나 방식으로 배치하더라도 항상 동일한 결과를 반환하는 연산을 의미합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
3
출력
12
설명
(x*(y*z)), (x*(z*y)), (y*(x*z)), (y*(z*x)), (z*(x*y)), (z*(y*x)),
((x*y)*z), ((y*x)*z), ((x*z)*y), ((z*x)*y), ((z*y)*x), ((y*z)*x).
해결 접근 방법
이 문제를 해결하기 위해서는 결과를 일반화할 수 있는 규칙성이나 수열 관계가 존재하는지 먼저 찾아보아야 합니다. 연산자의 개수에 따른 결합 연산의 수를 살펴보면 다음과 같습니다.
1 => 1
2 => 2
3 => 12
이제 이 규칙을 일반화해 보겠습니다. n개의 요소에 대한 결합 연산을 만든다고 가정하면, (n-1)개의 곱셈 연산자와 (n-1)개의 괄호를 배치하게 됩니다.
여기서 우리는 두 가지 방식으로 이들을 배열할 수 있습니다.
먼저 (n-1)개까지의 요소를 곱하는 경우의 수를 고려합니다. 그런 다음 마지막 요소 an을 결합 구조의 양쪽 끝 중 어느 곳에든 삽입할 수 있습니다. 이렇게 하면 n개의 연산자에 대해 2*2*(n-2)개의 새로운 결합이 만들어집니다.
다음으로 (a1, a2, … a(n-1))의 곱셈 결과에 an을 왼쪽 또는 오른쪽에 곱하는 방법을 고려하면, 추가로 두 가지 경우의 수가 발생합니다.
위의 두 경우를 더하면 n개의 연산자에 대한 총 결합 수를 구할 수 있습니다.
ass(n) = ((2*2*(n-2))(ass(n-1))) + 2*(ass(n-1))
ass(n) = (4n-8)(ass(n-1)) + 2*(ass(n-1))
ass(n) = (4n-6)(ass(n-1))
이 점화 관계는 유사 카탈란 수(Pseudo Catalan Number)와 동일한 공식과 초기값을 가지고 있습니다.
따라서 유사 카탈란 수의 일반 공식을 그대로 적용할 수 있습니다.
ass(n) = (2*n-2)! / (n-1)!
n = 5인 경우 공식이 어떻게 작동하는지 확인해 보겠습니다.
ass(5) = (2*5 - 2)! / (5-1)!
ass(5) = 8! / 4! = 40320 / 24 = 1680
C++ 구현 코드
결합 법칙을 이용해 n개의 요소를 곱하는 방법의 수를 찾는 프로그램은 다음과 같습니다.
예제 코드
#include<iostream>
using namespace std;
long int calcFactorial(int n){
if (n == 0 || n == 1)
return 1 ;
return n*calcFactorial(n-1);
}
long int calcWays ( int n ){
int N = 2*n - 2 ;
int R = n - 1 ;
return (calcFactorial((2*n)-2)/calcFactorial(n-1));
}
int main(){
int n = 7;
cout<<"The ways to multiply "<<n<<" elements with an associative operation : "<<calcWays(n);
return 0 ;
}
실행 결과
The ways to multiply 7 elements with an associative operation : 665280
마무리
정리하면, n개의 요소를 결합 법칙으로 곱하는 경우의 수는 유사 카탈란 수 공식인 (2n-2)! / (n-1)!로 계산할 수 있습니다. 재귀 함수로 팩토리얼을 구현한 뒤 공식에 대입하면 간단하고 효율적으로 답을 구할 수 있습니다. 다만 요소의 개수가 커질수록 값이 기하급수적으로 증가하므로, 오버플로우를 방지하려면 long long 타입 사용이나 모듈러 연산 적용을 고려하는 것이 좋습니다.