문제적남자 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;
	}

view raw HotBrain-E73.cpp hosted with ❤ by GitHub

	(function(){
	var log = document.getElementById('log');
	// 중복되는 숫자가 있는가?
	var duplCheck = function(s){
	var chk = {};
	for(var i=0; i<s.length; ++i){
	var k = parseInt(s[i]);
	if(chk[k] == true) break;
	chk[k] = true;
	if(i == s.length-1) return true;
	}
	};
	// x번째 숫자까지는 x로 나누어지는가?
	var correct = function(n){
	n = n+""; // casting to string
	var num = "";
	for(var i=0; i<n.length; ++i){
	num += n[i];
	if( parseInt(num) % (i+1) != 0 ) break;
	}
	return num.length == n.length;
	};
	var a = [ 0 ];
	for(var pos=1; pos<=10; ++pos){
	var str = '';
	var b = [], postfix = [];
	// 짝수번째는 2, 4, 6, 8 중 하나
	// 홀수번째는 0, 5 를 제외한 수 중 하나
	// 다섯번째는 5, 열번째는 0 이다.
	if(pos == 5) postfix = [5];
	else if(pos == 10) postfix = [0];
	else if(pos % 2) postfix = [1,2,3,4,6,7,8,9];
	else postfix = [2,4,6,8];
	for(var i in a){
	for(var p in postfix){
	var num = a[i]+""+postfix[p];
	if(duplCheck(num) && correct(num)){
	b.push(parseInt(num));
	str += '<span>' + parseInt(num) + '</span>&nbsp;';
	}
	}
	}
	a = b;
	str = pos +'번째 자리까지 가능한 숫자 ('+ a.length +'개)<br><div class="fold">' + str + '</div><hr>';
	log.innerHTML += str;
	}
	})();

view raw HotBrain-E73.js hosted with ❤ by GitHub