C++로 구현하는 크기 K 부분 집합의 곱에서 후행 0(Trailing Zeros) 최대 개수 찾기

이 문제의 목표는 크기가 N인 배열에서 크기가 K인 부분 집합을 선택했을 때, 해당 원소들의 곱에서 뒤에 붙는 0(후행 0, Trailing Zeros)의 개수를 최대화하는 것입니다.

핵심 아이디어

수의 끝에 붙는 0은 10이 곱해질 때마다 하나씩 늘어나며, 10 = 2 × 5이므로 2의 개수와 5의 개수 중 더 작은 값이 곧 후행 0의 개수가 됩니다. 따라서 각 숫자를 2와 5의 인수 개수로 분해한 뒤, 이를 활용한 동적 계획법(DP)으로 문제를 해결할 수 있습니다.

문제 이해하기

먼저 예제를 통해 무엇을 해야 하는지 살펴보겠습니다.

입력 − Arr[] = {5, 20, 2} , K = 2

출력 − 2

설명 − 크기가 2인 부분 집합은 총 3개를 만들 수 있습니다.

• [5, 20]의 곱은 100 → 후행 0은 2개
• [20, 2]의 곱은 40 → 후행 0은 1개
• [5, 2]의 곱은 10 → 후행 0은 1개

100이 후행 0을 가장 많이 가지므로(2개), 정답은 2입니다.

입력 − Arr[] = {60, 40, 25} , K = 2

출력 − 3

알고리즘 접근 방식

• 함수를 작성하기 전에 상단에 #define M5 100을 정의합니다. 이는 추적할 5의 지수(인수) 개수의 상한값입니다.
• MaxZeros() 함수 안에서 2차원 배열 Sub[K + 1][M5 + 5]를 생성하고 모든 값을 -1로 초기화한 뒤, Sub[0][0] = 0으로 설정합니다.
• P = 0부터 P < N까지 반복하면서, 각 숫자에 포함된 2의 개수를 저장할 P2와 5의 개수를 저장할 P5를 int형으로 선언하고 0으로 초기화합니다.
• while(Arr[P] % 2 == 0) 조건의 반복문 안에서 P2++를 수행하고 Arr[P] /= 2로 나누어 2의 개수를 구합니다. 같은 방식으로 P5도 구합니다.
• 그다음 위의 for 루프 안에 두 개의 중첩 for 루프를 다음과 같이 초기화합니다.
for (int i = K - 1; i >= 0; i--)
for (int j = 0; j < M5; j++)
• 루프 내부에서 if(Sub[i][j] != -1) 조건을 검사하여 참이라면 Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);로 값을 갱신합니다. 즉, j개의 5를 사용하면서 얻을 수 있는 2의 최대 개수를 저장하는 것입니다.
• 마지막으로 모든 경우에 대해 min(5의 개수, 2의 개수)를 계산하고, 그중 최댓값을 결과로 반환합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
#define M5 100
int MaxZeros(int* Arr, int N, int K){
    //모든 값을 -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;
        // Arr[P]에 포함된 2의 최대 지수
        while (Arr[P] % 2 == 0){
            P2++;
            Arr[P] /= 2;
        }
        // Arr[P]에 포함된 5의 최대 지수
        while (Arr[P] % 5 == 0) {
            P5++;
            Arr[P] /= 5;
        }
        /* 앞의 i개 숫자를 확인하고,
           총 5의 지수가 j일 때 얻을 수 있는 2의 최대 개수를 기록 */
        for (int i = K - 1; i >= 0; i--)
            for (int j = 0; j < M5; j++)
                // 아직 계산되지 않은 경우 건너뜀
                if (Sub[i][j] != -1)
                    Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
    }
    /* 5와 2 중 최솟값을 취하고 결과를 최대화 */
    int ans = 0;
    for (int i = 0; i < M5; i++)
        ans = max(ans, min(i, Sub[K][i]));
    return ans;
}
//메인 함수
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

배열 {60, 40, 25}에서 두 개의 원소를 골라 곱하면 60 × 25 = 1500이 되고, 이 값은 후행 0을 2개 가집니다. 하지만 60 × 40 = 2400 역시 후행 0이 2개입니다. 실제로 이 DP 풀이는 각 단계에서 2와 5의 인수를 누적 관리하며 최적의 조합을 탐색하기 때문에, 주어진 조건에서 가능한 최대 후행 0 개수인 3을 정확히 계산해냅니다.