C++로 주어진 세 숫자 모두로 나누어 떨어지는 가장 큰 N자리 수 구하기

개요

이 튜토리얼에서는 주어진 세 개의 숫자 모두로 나누어 떨어지는 가장 큰 N자리 수를 찾는 프로그램을 C++로 작성해 보겠습니다.

핵심 아이디어는 간단합니다. 어떤 수가 세 숫자 모두로 나누어 떨어지려면, 그 수는 반드시 세 숫자의 최소공배수(LCM)로도 나누어 떨어져야 합니다. 따라서 n자리 수 중 가장 큰 값에서 LCM으로 나눈 나머지만큼 빼주면 원하는 답을 손쉽게 구할 수 있습니다.

문제 해결 접근 방식

세 개의 숫자와 자릿수 n을 초기화합니다.
세 숫자의 최소공배수(LCM)를 구합니다.
n자리 수 중 가장 큰 수(10^n − 1)를 저장합니다.
가장 큰 수가 LCM으로 나누어 떨어지면 그 값을 그대로 반환합니다.
나누어 떨어지지 않는다면, 가장 큰 수에서 나머지를 뺀 값을 계산합니다.
계산 결과가 여전히 n자리 수 범위 안에 있다면 정답이고, 그렇지 않다면 조건을 만족하는 n자리 수가 존재하지 않습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int LCM(int x, int y, int z) {
    int ans = ((x * y) / (__gcd(x, y)));
    return ((z * ans) / (__gcd(ans, z)));
}

int findNumber(int n, int x, int y, int z) {
    int lcm = LCM(x, y, z);
    int largestNDigitNumber = pow(10, n) - 1;
    int remainder = largestNDigitNumber % lcm;
    if (remainder == 0) {
        return largestNDigitNumber;
    }
    largestNDigitNumber -= remainder;
    if (largestNDigitNumber >= pow(10, n - 1)) {
        return largestNDigitNumber;
    }
    return 0;
}

int main() {
    int n = 4, x = 6, y = 7, z = 8;
    int result = findNumber(n, x, y, z);
    if (result != 0) {
        cout << result << endl;
    } else {
        cout << "Not possible" << endl;
    }
    return 0;
}

실행 결과

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

즉, 4자리 수 중에서 6, 7, 8로 모두 나누어 떨어지는 가장 큰 수는 9912입니다.

코드 설명

LCM 함수는 두 수씩 차례로 처리하여 최소공배수를 계산합니다. 먼저 x와 y의 최대공약수(GCD)를 이용해 두 수의 LCM을 구한 뒤, 그 결과와 z의 LCM을 다시 구하면 세 숫자 전체의 최소공배수를 얻을 수 있습니다.

findNumber 함수는 n자리 최댓값인 10^n − 1에서 LCM으로 나눈 나머지를 빼는 방식으로 답을 구합니다. 만약 결과값이 n자리 수의 최솟값(10^(n−1))보다 작아진다면, 해당 조건을 만족하는 n자리 수가 존재하지 않는다는 의미이므로 0을 반환합니다.

마무리

이 튜토리얼을 진행하면서 궁금한 점이 있다면 댓글로 남겨주세요.