[해답] 특별한 10자리 숫자 (Matlab 코드)

아래의 문제의 해답을 Matlab을 이용하여 구해보았다.

$0$부터 $9$까지 $10$개의 숫자를 단 한번씩만 사용하여 다음의 규칙을 만족하는 $10$자리의 숫자를 만들어라: 모든 $1 \leq n \leq 10$에 대하여, 이 숫자의 앞에서부터 $n$자리 까지가 $n$으로 나누어 떨어진다.

코드 실행시간을 줄이기 위하여 총 세가지 시도를 해 보았는데 각각은 다음과 같다.

1. 무작정 $10! = 3628800$ 가지 경우를 모두 체크
2. $a_{5}=5$, $a_{10}=0$임을 이용하여 $8! = 40320$ 가지 경우를 체크
3. 2번 조건에 추가로 $a_{2},\, a_{4},\, a_{6},\, a_{8} \in \{ 2,\, 4,\, 5,\, 8 \}$, $a_{1},\, a_{3},\, a_{7},\, a_{9} \in \{ 1,\, 3,\, 7,\, 9 \}$임을 이용하여 $4! \times 4! = 576$ 가지 경우를 체크

위 세가지 시도의 결과와 각각이 걸린 시간은 아래와 같다.

>> 10digitnum
the number is 3816547290 
경과 시간은 79.544595초입니다.
>> 10digitnum
the number is 3816547290 
경과 시간은 0.943648초입니다.
>> 10digitnum
the number is 3816547290 
경과 시간은 0.022766초입니다.

Matlab 코드

tic;
% First attempt:
% I = [ 1 2 3 4 5 6 7 8 9 0 ];
% N = perms( I ); k = size( N, 1 );

% Second attempt:
% I = [ 1 2 3 4 6 7 8 9 ];
% N = perms( I ); k = size( N, 1 );
% N = [ N( :, 1:4 ) 5*ones( k, 1 ) N( :, 5:8 ) zeros( k, 1 ) ];

% Third attempt:
I = [ 1 3 7 9 ]; J = [ 2 4 6 8 ];
N = perms( I ); M = perms( J ); k1 = size( N, 1 );
N = kron( ones( k1, 1 ), N ); M = kron ( M, ones( k1, 1 ) ); k = size( N, 1 );
N = [ N( :, 1 ) M( :, 1 ) N( :, 2 ) M( :, 2 ) 5*ones( k, 1 )...
    M( :, 3 ) N( :, 3 ) M( :, 4 ) N( :, 4 ) zeros( k, 1 ) ];

for m = 1 : k
    flag = 0;
    for n = 1 : 10
        if rem( 10.^( n-1:-1:0 )*N( m, 1:n )', n) ~= 0
            flag = 1;
            break
        end  
    end
    if flag == 0
        num = 10.^( 9:-1:0 )*N( m, : )';
        fprintf( 'the number is %d \n', num );
    end
end
toc;