문제

어떤 수 N이 주어졌을 때, N으로 시작하면서, N의 0이 아닌 모든 자리수로 나누어지는 떨어지는 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 어떤 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 답을 출력한다.

문제가 굉장히 심플하다.

접근 과정

결과 값은 0을 제외한 모든 자릿수의 최소 공배수에 나누어 떨어진다. a와 b의 최소 공배수는
[ \(a \times b / (최대공약수)\) ]
로 구할 수 있으며. 여기서 최대 공약수를 구하고자 유클리드 호제법을 이용한 gcd() 함수를 구현하였다.
이제 앞자리가 N으로 시작하는 모든 숫자에 대해 1번에서 구한 최소 공배수로 나눠서 확인해주면 된다. N에다 10씩 곱하고 N 부분이 변하지 않는 범위에서 확인해보고 범위를 넘어서면 다시 10을 곱하여 반복하는 식이다. 다른 사람들의 코드를 봤을 때 이렇게 전부 탐색 하더라도 시간초과 위험은 없어보였다.
그래도 본인은 약간의 최적화를 첨가했는데 \(N \times 10^k\)를 최대 공배수로 나눴을 떄 나머지가 \(10^k\) 보다 크다면 현재 자릿수에서는 최대 공배수로 나누어 떨어지는 경우가 없으므로 다음 자릿수를 확인하는 방식이다.

소스 코드

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int getSelectiveLcm(int n) {
    int ret = 1;
    bool hasDigit[10] = {false,};
    while (n > 0) {
        int digit = n % 10;
        if (digit != 0 && !hasDigit[digit]) {
            int _gcd = ret >= digit ? gcd(ret, digit) : gcd(digit, ret);
            ret = ret * digit / _gcd;
            hasDigit[digit] = true;
        }
        n /= 10;
    }
    return ret;
}

int main(void) {
    long long res;
    int n, lcm, rem;

    cin >> n;
    lcm = getSelectiveLcm(n);
    
    int exp = 1;
    res = n;
    rem = res % lcm;
    while (rem != 0) {
        int diff = lcm - rem;
        if (diff == lcm || diff < exp) {
            res += diff;
            break;
        }
        exp *= 10;
        res *= 10;
        rem = res % lcm;
    }

    cout << res << endl;
    return 0;
}