시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19859 10423 8471 53.600%

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

예제 입력 1


						

예제 출력 1

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993
W3sicHJvYmxlbV9pZCI6IjQ2NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxNDBcdWQ1MDQgXHViMTE4XHViYzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxNDBcdWQ1MDQgXHViMTE4XHViYzg0XHViMjk0IDE5NDlcdWIxNDQgXHVjNzc4XHViM2M0IFx1YzIxOFx1ZDU1OVx1Yzc5MCBELlIuIEthcHJla2FyXHVhYzAwIFx1Yzc3NFx1Yjk4NCBcdWJkOTlcdWM2MDBcdWIyZTQuIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgZChuKVx1Yzc0NCBuXHVhY2ZjIG5cdWM3NTggXHVhYzAxIFx1Yzc5MFx1YjlhY1x1YzIxOFx1Yjk3YyBcdWIzNTRcdWQ1NThcdWIyOTQgXHVkNTY4XHVjMjE4XHViNzdjXHVhY2UwIFx1YzgxNVx1Yzc1OFx1ZDU1OFx1Yzc5MC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgZCg3NSkgPSA3NSs3KzUgPSA4N1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWI5N2MgXHVjMmRjXHVjNzkxXHVkNTc0XHVjMTFjIG4sIGQobiksIGQoZChuKSksIGQoZChkKG4pKSksIC4uLlx1YWNmYyBcdWFjMTlcdWM3NDAgXHViYjM0XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMzNcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0XHViYTc0IFx1YjJlNFx1Yzc0YyBcdWMyMThcdWIyOTQgMzMgKyAzICsgMyA9IDM5XHVjNzc0XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzIxOFx1YjI5NCAzOSArIDMgKyA5ID0gNTEsIFx1YjJlNFx1Yzc0YyBcdWMyMThcdWIyOTQgNTEgKyA1ICsgMSA9IDU3XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZjBcdWMyZGRcdWM3M2NcdWI4NWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjMzLCAzOSwgNTEsIDU3LCA2OSwgODQsIDk2LCAxMTEsIDExNCwgMTIwLCAxMjMsIDEyOSwgMTQxLCAuLi48XC9wPlxyXG5cclxuPHA+blx1Yzc0NCBkKG4pXHVjNzU4IFx1YzBkZFx1YzEzMVx1Yzc5MFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgMzNcdWM3NDAgMzlcdWM3NTggXHVjMGRkXHVjMTMxXHVjNzkwXHVjNzc0XHVhY2UwLCAzOVx1YjI5NCA1MVx1Yzc1OCBcdWMwZGRcdWMxMzFcdWM3OTAsIDUxXHVjNzQwIDU3XHVjNzU4IFx1YzBkZFx1YzEzMVx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVjMGRkXHVjMTMxXHVjNzkwXHVhYzAwIFx1ZDU1YyBcdWFjMWNcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzQwIFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDEwMVx1Yzc0MCBcdWMwZGRcdWMxMzFcdWM3OTBcdWFjMDAgMlx1YWMxYyg5MVx1YWNmYyAxMDApIFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjMGRkXHVjMTMxXHVjNzkwXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjMTQwXHVkNTA0IFx1YjExOFx1YmM4NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIDEwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjMTQwXHVkNTA0IFx1YjExOFx1YmM4NFx1YjI5NCBcdWNkMWQgMTNcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LiAxLCAzLCA1LCA3LCA5LCAyMCwgMzEsIDQyLCA1MywgNjQsIDc1LCA4NiwgOTc8XC9wPlxyXG5cclxuPHA+MTAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxNDBcdWQ1MDQgXHViMTE4XHViYzg0XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVjNlx1YjJlNDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPjEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzE0MFx1ZDUwNCBcdWIxMThcdWJjODRcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDY3MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlbGYgTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gMTk0OSB0aGUgSW5kaWFuIG1hdGhlbWF0aWNpYW4gRC5SLiBLYXByZWthciBkaXNjb3ZlcmVkIGEgY2xhc3Mgb2YgbnVtYmVycyBjYWxsZWQgc2VsZi1udW1iZXJzLiBGb3IgYW55IHBvc2l0aXZlIGludGVnZXIgbiwgZGVmaW5lIGQobikgdG8gYmUgbiBwbHVzIHRoZSBzdW0gb2YgdGhlIGRpZ2l0cyBvZiBuLiAoVGhlIGQgc3RhbmRzIGZvciBkaWdpdGFkaXRpb24sIGEgdGVybSBjb2luZWQgYnkgS2FwcmVrYXIuKSBGb3IgZXhhbXBsZSwgZCg3NSkgPSA3NSArIDcgKyA1ID0gODcuIEdpdmVuIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIG4gYXMgYSBzdGFydGluZyBwb2ludCwgeW91IGNhbiBjb25zdHJ1Y3QgdGhlIGluZmluaXRlIGluY3JlYXNpbmcgc2VxdWVuY2Ugb2YgaW50ZWdlcnMgbiwgZChuKSwgZChkKG4pKSwgZChkKGQobikpKSwgLi4uLiBGb3IgZXhhbXBsZSwgaWYgeW91IHN0YXJ0IHdpdGggMzMsIHRoZSBuZXh0IG51bWJlciBpcyAzMyArIDMgKyAzID0gMzksIHRoZSBuZXh0IGlzIDM5ICsgMyArIDkgPSA1MSwgdGhlIG5leHQgaXMgNTEgKyA1ICsgMSA9IDU3LCBhbmQgc28geW91IGdlbmVyYXRlIHRoZSBzZXF1ZW5jZTxcL3A+XHJcblxyXG48cD4zMywgMzksIDUxLCA1NywgNjksIDg0LCA5NiwgMTExLCAxMTQsIDEyMCwgMTIzLCAxMjksIDE0MSwgLi4uPFwvcD5cclxuXHJcbjxwPlRoZSBudW1iZXIgbiBpcyBjYWxsZWQgYSBnZW5lcmF0b3Igb2YgZChuKS4gSW4gdGhlIHNlcXVlbmNlIGFib3ZlLCAzMyBpcyBhIGdlbmVyYXRvciBvZiAzOSwgMzkgaXMgYSBnZW5lcmF0b3Igb2YgNTEsIDUxIGlzIGEgZ2VuZXJhdG9yIG9mIDU3LCBhbmQgc28gb24uIFNvbWUgbnVtYmVycyBoYXZlIG1vcmUgdGhhbiBvbmUgZ2VuZXJhdG9yOiBmb3IgZXhhbXBsZSwgMTAxIGhhcyB0d28gZ2VuZXJhdG9ycywgOTEgYW5kIDEwMC4gQSBudW1iZXIgd2l0aCBubyBnZW5lcmF0b3JzIGlzIGEgc2VsZi1udW1iZXIuIFRoZXJlIGFyZSB0aGlydGVlbiBzZWxmLW51bWJlcnMgbGVzcyB0aGFuIDEwMDogMSwgMywgNSwgNywgOSwgMjAsIDMxLCA0MiwgNTMsIDY0LCA3NSwgODYsIGFuZCA5Ny48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIG91dHB1dCBhbGwgcG9zaXRpdmUgc2VsZi1udW1iZXJzIGxlc3MgdGhhbiAxMDAwMCBpbiBpbmNyZWFzaW5nIG9yZGVyLCBvbmUgcGVyIGxpbmUuPFwvcD5cclxuIiwiaW5wdXQiOiIiLCJvdXRwdXQiOiIiLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

채점

  • 예제는 채점하지 않는다.