제곱수란 어떤 정수 x의 제곱으로 나타낼 수 있는 숫자를 말한다.

예를 들어 한자리수인 제곱수는 0(0*0), 1(1*1), 4(2*2), 9(3*3)가 있다.

최근 정보올림피아드 예선 준비로 수학에 재미를 느끼고 있는 경완이는 한자리 제곱수로 만 표현되는 숫자들이 어떤 것들이 있는지 알고자 한다.

다시 말해서 0, 1, 4, 9의 숫자로만 구성되고, 숫자 앞에 0이 붙지 않은 숫자가 어떤 것들이 있는지 알고자 한다.

처음 등장하는 0을 0번째라고 하고, 오름차순으로 이러한 숫자를 정렬한 결과는 다음과 같다.

0, 1, 4, 9, 10, 11, 14, 19, 40, 41, 44, 49, ...

나타나는 번째 수를 뜻하는 N을 입력 받았을 때,

N에 대응 되는 조건을 만족하는 숫자가 무엇인지 알아내는 프로그램을 작성하여 경완이의 호기심을 충족시켜주자.

제곱수로 이루어진 숫자 timer 1s memory 256MB

제곱수로 이루어진 숫자 1s 256MB