표지판 > 문제은행



문제은행

3168 : 표지판

제한시간: 7000 ms    메모리제한: 256 MB
해결횟수: 4 회    시도횟수: 82 회   



조이는 길이 막히는 차에서 너무 지루한 나머지 숫자놀이를 하기로 했다. 먼저 마음속으로 숫자 K를 정한다. 그 다음, K자리이면서 모든 숫자가 0 이상 K 이하인 표지판을 하나 고른다. 이제 이 숫자를 다른 숫자로 바꾸는데, 1번째 자리가 1의 개수고, 2번째 자리가 2의 개수고, ..., K번째 자리가 K의 개수인 K자리 숫자를 만든다.

조이는 놀이를 하다가 하나 궁금한 점이 생겼다. 조이가 표지판을 봤을 때, 그 표지판의 숫자를 만들 수 있는 표지판이 몇 가지나 있는지 궁금했다. 이 표지판은 K자리이고, 모든 자리수가 0 이상 K 이하여야 한다는 점에 유의하자. 하지만 조이에게는 너무 어려운 문제였기 때문에, 여러분에게 도움을 청했다.

 

조이가 0414라는 표지판을 봤다고 해보자. 이 표지판은 11, 20, 30, 42개이기 때문에 1002로 바뀐다. 이 숫자를 여러번 바꾸면 1100, 2000, 0100, 1000 순서로 바뀌게 된다. 1000은 항상 자기 자신으로 바뀐다. , 1000을 만들 수 있는 표지판에는 1000, 0100, 2000, 1100, 1002, 0414 등이 있다.

 

표지판의 번호가 주어졌을 때, 표지판의 번호를 만들 수 있는 숫자의 개수를 구해주자. 




첫 번째 줄에 테스트케이스의 개수 T가 주어진다. (1≦T≦100)
두 번째 줄부터 T개의 줄에 표지판의 번호 G가 주어진다. G의 자릿수가 K임이 보장된다.

[제한]
부분 문제 1 [25점]
G의 자릿수가 5 이하이다.
부분 문제 2 [75점]
G의 자릿수가 9 이하이다.



T개의 줄에 각 테스트케이스에 대한 G를 만들 수 있는 표지판의 개수를 출력한다.


3
20
1
123
4
1
1


첫 번째 예제는 자기 자신인 20, 한 번 바꿔서 20을 만들 수 있는 11, 두 번 바꿔서 20을 만들 수 있는 12, 21이 있어 총 4개이다.






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.