이 튜토리얼에서는 주어진 숫자 배열의 자릿수들을 조합하여 만들 수 있는 수 중에서 2, 3, 5로 모두 나누어 떨어지는 가장 큰 수를 찾는 프로그램을 C++로 작성해 보겠습니다.
문제 해결 접근 방식
어떤 수가 2, 3, 5로 동시에 나누어 떨어지려면 다음 조건을 만족해야 합니다.
- 30의 배수여야 하므로, 수의 끝자리는 반드시 0이어야 합니다(2와 5의 배수 조건).
- 모든 자릿수의 합이 3으로 나누어 떨어져야 합니다.
이 두 조건을 바탕으로 문제를 단계별로 해결해 보겠습니다.
알고리즘 단계
- 배열을 초기화합니다.
- 배열 안에 0이 존재하는지 확인하고, 0이 없다면 조건을 만족하는 수를 만들 수 없으므로 "불가능"을 출력합니다.
- 배열을 내림차순으로 정렬합니다. 정렬 후 첫 번째 원소가 0이라면 배열 전체가 0뿐이므로 결과는 0입니다.
- 모든 자릿수의 합을 3으로 나눈 나머지(sum % 3)를 구합니다.
- 나머지가 0이 아니라면, 각 자릿수를 3으로 나눈 나머지가 위에서 구한 나머지와 같은 자릿수를 하나 찾아 제거합니다. 이렇게 하면 전체 합이 3의 배수가 됩니다.
- 만약 해당 나머지와 같은 자릿수가 하나도 없다면, 나머지를 (3 - 나머지)로 변경하고 그 나머지와 일치하는 자릿수 두 개를 제거합니다. 예를 들어 나머지가 1인데 나머지가 1인 자릿수가 없다면, 나머지가 2인 자릿수 두 개를 제거하면 됩니다.
- 최종적으로 배열에 남은 자릿수를 순서대로 출력합니다.
예제 코드
위 알고리즘을 실제 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
void findLargestDivibleNumber(int n, vector<int>& v){
int flag = 0;
long long sum = 0;
for (int i = 0; i < n; i++) {
if (v[i] == 0) {
flag = 1;
}
sum += v[i];
}
if (!flag) {
cout << "Not possible" << endl;
}else {
sort(v.begin(), v.end(), greater<int>());
if (v[0] == 0) {
cout << "0" << endl;
}else {
int flag = 0;
int remainder = sum % 3;
if (remainder != 0) {
for (int i = n - 1; i >= 0; i--) {
if (v[i] % 3 == remainder) {
v.erase(v.begin() + i);
flag = 1;
break;
}
}
if (flag == 0) {
remainder = 3 - remainder;
int count = 0;
for (int i = n - 1; i >= 0; i--) {
if (v[i] % 3 == remainder) {
v.erase(v.begin() + i);
count++;
if (count >= 2) {
break;
}
}
}
}
}
if (*v.begin() == 0) {
cout << "0" << endl;
}else {
for (int i : v) {
cout << i;
}
}
}
}
}
int main() {
int n = 9;
vector<int> v{ 4, 5, 0, 3, 2, 4, 5, 6, 7 };
findLargestDivibleNumber(n, v);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
765544320
입력 배열 {4, 5, 0, 3, 2, 4, 5, 6, 7}에서 자릿수 합은 36이므로 3으로 나누어 떨어지고, 0도 포함되어 있습니다. 따라서 자릿수를 제거할 필요 없이 내림차순으로 정렬된 765544320이 최종 결과가 됩니다. 이 수는 2, 3, 5로 모두 나누어 떨어집니다.
마무리
이번 튜토리얼에서는 배열의 자릿수로 만들 수 있는 수 중 2, 3, 5로 나누어 떨어지는 가장 큰 수를 찾는 방법을 알아보았습니다. 핵심은 끝자리 0의 존재 여부 확인과 자릿수 합의 3 배수 조건을 맞추기 위한 자릿수 제거 로직입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.