문제 소개
정수로 이루어진 배열 arr[]가 주어졌을 때, 배열의 모든 요소를 곱한 값의 약수(제수) 개수를 계산하는 것이 목표입니다.
배열은 동일한 자료형의 요소들을 고정된 크기만큼 순차적으로 저장할 수 있는 대표적인 자료구조입니다. 배열은 데이터 집합을 저장하는 용도로 사용되며, 같은 타입의 변수들이 모인 컬렉션으로 생각하면 더욱 직관적으로 이해할 수 있습니다.
예시
입력 − int arr[] = {2, 3}
출력 − count is 4설명 − 배열 요소의 곱은 2 × 3 = 6이며, 6의 약수는 1, 2, 3, 6입니다. 따라서 6의 약수는 총 4개입니다.
입력 − int arr[] = {2, 3, 5}
출력 − count is 8설명 − 배열 요소의 곱은 2 × 3 × 5 = 30이며, 30의 약수는 1, 2, 3, 5, 6, 10, 15, 30입니다. 따라서 30의 약수는 총 8개입니다.
해결 접근 방식
- 배열 arr[]를 생성합니다.
- 배열의 길이를 계산합니다. C++에서는 sizeof 연산자를 활용해 배열에 포함된 요소 수를 정수 값으로 얻을 수 있습니다.
- 임시 변수 temp를 선언하고 1로 초기화합니다.
- i를 0부터 시작하여 배열 크기보다 작을 때까지 반복하는 루프를 실행합니다.
- 각 반복마다 temp *= arr[i]로 배열 요소를 누적하여 곱합니다.
- 약수 개수를 반환하는 별도의 함수를 호출합니다.
- 약수의 개수를 저장할 임시 변수를 준비합니다.
- i를 1부터 곱한 값까지 반복하는 루프를 실행합니다.
- 루프 안에서 곱한 값 % i == 0이면 count를 1 증가시킵니다.
- count를 반환하고 결과를 출력합니다.
예제 코드
#include <iostream>
using namespace std;
// 주어진 수의 약수 개수를 세는 함수
int divisors(int N){
// 결과값을 0으로 초기화
int result = 0;
// 주어진 수 N의 모든 약수에 대해 결과값 증가
for (int i = 1; i <= N; ++i){
if (N % i == 0){
result++;
}
}
return result;
}
// 배열의 모든 요소를 곱한 후 약수 개수를 구하는 함수
int countmultiples(int arr_1[], int size){
// 배열의 모든 요소를 곱함
int temp = 1;
for (int i = 0; i < size; ++i){
temp *= arr_1[i];
}
return divisors(temp);
}
// 메인 함수
int main(){
int arr_1[] = { 5, 10, 15 };
int size = sizeof(arr_1) / sizeof(arr_1[0]);
cout << "count is " << countmultiples(arr_1, size);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 −
count is 16
설명 − 배열 요소의 곱은 5 × 10 × 15 = 750입니다. 750 = 2¹ × 3¹ × 5³이므로 약수의 개수는 (1+1) × (1+1) × (3+1) = 16개입니다.
효율성 참고 사항
위 방법은 곱한 값의 크기만큼 1부터 반복 검사하기 때문에 O(N)의 시간 복잡도를 가집니다. 따라서 배열 요소의 곱이 매우 커지면 실행 시간이 급격히 늘어날 수 있습니다. 이런 경우 소인수분해를 활용하면 훨씬 효율적으로 약수 개수를 구할 수 있습니다. N = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ로 소인수분해되었다면, 약수의 개수는 (a₁+1) × (a₂+1) × … × (aₖ+1) 공식으로 바로 계산할 수 있습니다.