M 자리 배열과 함께 숫자 N을 지정했습니다. 우리의 임무는 5로 나누어 떨어지는 주어진 M 자리에서 형성된 n자리 숫자의 수를 찾는 것입니다.
문제 입력 및 출력을 이해하기 위해 몇 가지 예를 살펴보겠습니다.
안에 -
N = 2
M = 3
arr = {5, 6, 3} 아웃 -
2
5로 나눌 수 있는 2개의 N자리 숫자 35와 65가 있습니다. 다른 예를 살펴보겠습니다.
입력 -
N = 1
M = 7
arr = {2, 3, 4, 5, 6, 7, 8} 출력 -
1
주어진 배열에서 5로 나눌 수 있는 1자리 숫자는 1개뿐입니다. 따라서 우리의 임무는 5로 나누어 떨어지는 N자리 숫자로 구성될 수 있는 숫자의 개수를 찾는 것입니다.
숫자는 5로 나누어 떨어지려면 0 또는 5의 숫자로 끝나야 합니다. 알고리즘을 살펴보겠습니다.
알고리즘
- 주어진 배열에서 0과 5를 확인합니다. 2. 0과 5가 모두 있는 경우 단위 자리에 숫자를 배치하는 두 가지 방법이 있습니다. 그렇지 않으면 한 가지 방법으로 숫자를 배치할 수 있습니다.
- 카운트를 2로 초기화합니다.
- 이제 남은 자리는 m - 1, m - 2, m - 3, ... n 가지 방법으로 각각 채울 수 있습니다.
- 0에서 n - 1까지 반복하는 루프를 작성합니다.
- 배열의 크기를 줄입니다.
- 수를 곱합니다.
- 한 자리 숫자 0 또는 5가 있는 경우 단위 자리에 숫자를 배치하는 방법은 한 가지뿐입니다.
- 카운트를 2로 초기화합니다.
- 이제 남은 자리는 m - 1, m - 2, m - 3, ... n 가지 방법으로 각각 채울 수 있습니다.
- 0에서 n - 1까지 반복하는 루프를 작성합니다.
- 배열의 크기를 줄입니다.
- 수를 곱합니다.
- 0이나 5가 없으면 5로 나눌 수 있는 숫자를 만들 수 있습니다. 이 경우 -1을 반환합니다.
구현
다음은 위의 알고리즘을 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;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
2