C++로 M개의 숫자를 조합해 만들 수 있는 5의 배수 N자리 수 개수 구하기

숫자 N과 M개의 숫자로 이루어진 배열이 주어졌을 때, 주어진 숫자들을 조합하여 만들 수 있는 N자리 수 중에서 5로 나누어 떨어지는 수의 개수를 구하는 것이 이번 문제의 목표입니다.

문제 이해하기

예시를 통해 문제의 입력과 출력을 먼저 살펴보겠습니다.

입력 −

N = 2
M = 3
arr = {5, 6, 3}

출력 −

주어진 배열의 숫자들로 만들 수 있는 2자리 수 중에서는 35와 65, 두 개의 수가 5로 나누어 떨어집니다.

다른 예시도 확인해 보겠습니다.

입력 −

N = 1
M = 7
arr = {2, 3, 4, 5, 6, 7, 8}

출력 −

주어진 배열에서 한 자리 수로 5로 나누어 떨어지는 수는 5 하나뿐입니다. 즉, 이 문제는 주어진 숫자들로 만들 수 있는 N자리 수 중 5의 배수가 되는 수가 몇 개인지 세는 것입니다.

접근 방법

어떤 수가 5로 나누어 떨어지려면 반드시 0 또는 5로 끝나야 합니다. 따라서 일의 자리에 올 수 있는 숫자의 가짓수를 먼저 파악한 뒤, 나머지 자리를 채우는 경우의 수를 곱해주면 됩니다.

알고리즘 단계

주어진 배열에 0과 5가 있는지 확인합니다.
0과 5가 모두 있는 경우: 일의 자리에 놓을 수 있는 방법이 두 가지이므로 count를 2로 초기화합니다.
0 또는 5 중 하나만 있는 경우: 일의 자리에 놓을 수 있는 방법이 한 가지이므로 count를 1로 초기화합니다.
남은 n−1개의 자리를 차례로 채웁니다. 각 자리를 채울 때마다 사용 가능한 숫자가 하나씩 줄어들므로 m−1, m−2, m−3, … 순으로 경우의 수가 감소합니다.
0부터 n−1까지 반복하는 루프 안에서 배열의 크기(m)를 1씩 감소시키고, 그 값을 count에 곱합니다.
배열에 0과 5가 모두 없다면 5로 나누어 떨어지는 수를 만들 수 없으므로 −1을 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>

using namespace std;

int numbers(int n, int m, int arr[]) {
    bool isZeroPresent = false, isFivePresent = false;
    int numbersCount = 0;
    if (m < n) {
        return -1;
    }
    for (int i = 0; i < m; i++) {
        if (arr[i] == 0) {
            isZeroPresent = true;
        }
        if (arr[i] == 5) {
            isFivePresent = true;
        }
    }
    if (isZeroPresent && isFivePresent) {
        numbersCount = 2;
        for (int i = 0; i < n - 1; i++) {
            m--;
            numbersCount = numbersCount * m;
        }
    } else if (isZeroPresent || isFivePresent) {
        numbersCount = 1;
        for (int i = 0; i < n - 1; i++) {
            m--;
            numbersCount = numbersCount * m;
        }
    } else {
        return -1;
    }
    return numbersCount;
}

int main() {
    int arr[] = {5, 6, 3};
    cout << numbers(2, 3, arr) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.