문제적남자 73화:수학 - 코딩으로 풀어보기

문제적남자 73화 - 수학 풀이

수능 D-100 특집으로 이런 문제가 나왔다.

첫 번째 숫자까지는 1로 나누어지고,

두 번째 숫자까지는 2로, .... 열 번째 숫자까지는 10으로 나누어진다.

0부터 9까지 10개의 숫자를 모두 사용해 규칙에 맞는 수를 만들어라.

다음과 같은 몇 가지 규칙을 발견하고 브루트 포스로 풀어보기로 했다.

1. 열 번째 숫자는 0 이다. (10의 배수는 0으로 끝나기 때문)
2. 다섯 번째 숫자는 5 이다. (5의 배수는 0, 5로 끝난다. 0은 열 번째 숫자이므로 5)
3. 짝수 번째 숫자는 2, 4, 6, 8 중 하나이다.
4. 홀수 번째 숫자는 1, 2, 3, 4, 6, 7, 8, 9 중 하나이다.

소스: https://jsfiddle.net/J00nas/yrmen84L/

javascript로 적어봤는데, 비동기식이라 그런지 제대로 걸러지지가 않는다. (그리고 브라우저의 자바스크립트 버전별로 다르게 보일 수 있다.) 그래도 답은 나온다.

모던 브라우저에서는 위처럼 보일것이다.

자바스크립트로는 코드가 정확하지 않은 것 같아서 C++로 다시 적었다.
소스: https://ideone.com/yoLJXx

신기하게도 규칙을 만족하는 숫자는 3816547290 뿐이었다.

#include <cstdio>
#include <vector>
using namespace std;

typedef long long lld;

// 중복되는 숫자가 있는가
bool duplCheck(lld n){
    bool fq[10]={};
    while(n>0){
        if(fq[n%10]) return false;
        fq[n%10] = true;
        n /= 10;
    }
    return true;
}

// x번째 숫자까지는 x로 나누어지는가
bool correct(lld n){
    int len = 0;
    for(lld t=n; t>0; t/=10) len += 1;

    for(int pos=len; len>0 && n>0; --len, n/=10){
        if( n % len != 0 ) return false;
    }
    return true;
}

lld postlen[4]={1,1,8,4};
lld postfix[4][10]={
    {5}, {0}, {1,2,3,4,6,7,8,9}, {2,4,6,8}
};

int main(){
    vector<lld> a(1, 0);

    for(int pos=1; pos<=10; ++pos){
        vector<lld> b;
        // 짝수번째는 2, 4, 6, 8 중 하나
        // 홀수번째는 0, 5 를 제외한 수 중 하나
        // 다섯번째는 5, 열번째는 0 이다.
        int pf = 3;
        if(pos == 5) pf = 0;
        else if(pos == 10) pf = 1;
        else if(pos % 2) pf = 2;

        for(int i=0; i<a.size(); ++i){
            for(int j=0; j<postlen[pf]; ++j){
                lld num = a[i]*10 + postfix[pf][j];
                if(duplCheck(num) && correct(num)){
                    b.push_back(num);
                    printf("%lld ", num);
                }
            }
        }
        a = b;
        printf("\n%d번째 숫자까지 가능한 수: %d개\n\n", pos, a.size());
    }
    return 0;
}