주어진 작업은 크기 N의 주어진 배열의 크기 K의 하위 집합의 곱에서 후행 0의 최대 수를 찾는 것입니다.
이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -
입력 - Arr[] ={5, 20, 2}, K=2
출력 - 2
설명 − 크기 =2인 총 3개의 하위 집합을 만들 수 있습니다.
[5, 20]의 곱은 100입니다.
[20, 2]의 곱은 40입니다.
[5, 2]의 곱은 10입니다.
100은 후행 0의 최대 개수 =2를 갖습니다. 따라서 2가 답입니다.
입력 - Arr[] ={60, 40, 25} , K=2
출력 - 3
아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
-
기능 시작 전 상단에 #define M5 100
-
MaxZeros() 함수에서 2D 배열 Sub[K + 1][M5 + 5]를 만들고 각 값을 -1로 초기화하고 Sub[0][0] =0;
으로 설정합니다. -
P=0에서 P
-
while(Arr[P]%2 ==0) 조건으로 while 루프를 시작하고 루프 내부에서 P2++ 및 Arr[P]/2를 수행하여 2의 개수를 얻습니다. P5에 대해 동일한 단계를 반복합니다.
-
그런 다음 위의 시작된 For 루프 내부에서 다음과 같이 두 개의 중첩 for 루프를 초기화합니다. -
for (int i =K - 1, i>=0, i--)
(int j =0; j
-
이 루프 내에서 if(Sub[i][j] !=-1) 확인하고 그것이 참이면 Sub[i + 1][j + P5] =max(Sub[i + 1];[j + P5 ], 하위[i][j] + P2);
예시
#include <bits/stdc++.h>
using namespace std;
#define M5 100
int MaxZeros(int* Arr, int N, int K){
//Initializing each value with -1;
int Sub[K+1][M5+5];
memset(Sub, -1, sizeof(Sub));
Sub[0][0] = 0;
for (int P = 0; P < N; P++){
int P2 = 0, P5 = 0;
// Maximal power of 2 in Arr[P]
while (Arr[P] % 2 == 0){
P2++;
Arr[P] /= 2;
}
// Maximal power of 2 in Arr[P]
while (Arr[P] % 5 == 0) {
P5++;
Arr[P] /= 5;
}
/* We can collect 2s by checking first i numbers and taking their j with total power of 5*/
for (int i = K - 1; i >= 0; i--)
for (int j = 0; j < M5; j++)
// If subset[i][j] is not calculated.
if (Sub[i][j] != -1)
Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
}
/* Taking minimum of 5 or 2 and maximizing the result*/
int ans = 0;
for (int i = 0; i < M5; i++)
ans = max(ans, min(i, Sub[K][i]));
return ans;
}
//Main function
int main(){
int Arr[] = { 60, 40, 25 };
int K = 2;
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << MaxZeros(Arr, N, K);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 -
3