http://news.zum.com/articles/2829610
구글 입사 문제중에 1에서 10000까지 8이 몇개 나오는지 세보라는 문제가 있다고 한다.
나의 해법.
a=0
for i in range(10000):
n=i+1
while(n>0):
a+=int(((n+2)%10)==0)
n/=10
print(a)
몇자 더 줄인 버전.
a=0
i=10000
while(i>0):
while(n>0):
a+=int((n%10)==8)
n/=10
i-=1
print(a)
증명.
1. (n%10)은 n을 10으로 나눈 나머지이다.
2. (n%10)이 8인 경우 (n%10)==8은 True이다.
3. (n%10)이 8이 아닌 경우 (n%10)==8은 False이다.
4. Python에서 int(True)는 1이다.
5. Python에서 int(False)는 0이다.
6. a+=x는 a에 a+x를 대응시킨다.
7. 1~6에 의해, a+=int((n%10)==8)이 실행되면, n의 1의 자리에 있는 수가 8이면 a는 1만큼 커지고, 8이 아니면 변하지 않는다.
8. n/=10은 n에 n을10으로 나눈 몫을 대응시킨다. 이때, n과 10이 모두 int형이면 나머지는 버려진다.
9. while(n>0)은 n이 0보다 커야 수행되고 0이거나 0보다 작으면 수행되지 않는다.
10. 가장 마지막으로 수행되는 경우는 n이 한자리 수이고, 이후에 n/=10을 수행하면 n=0이 되어 있다.
11. 따라서 while(n>0)구문이 수행되고 나면 a는 n에 있는 8의 수만큼 증가한다.
12. 따라서 while(i>0)구문이 수행되면 1부터 10000사이에 있는 각 정수들이 가지고 있는 8의 수를 셀 수 있다.
그렇군요. 감사합니다.
그나저나 새 글은 언제 올리시나요 ㅎㅎ
첫째줄에 1부터 10까지 쓰기 시작하면, 여덟번? 컬럼의 일의 자리에 8이 써있고, 1000줄이므로 8이 일단 1000개가 사용됩니다.
매 10행마다 8번째 행은 8이 십의 자리에 써있고, 그 숫자가 10개가 연속으로 옆으로 써있으므로 1000개의 8이 더 사용됩니다.
매 100행마다 80번째 행은 8이 백의 자리 수이고 그 행은 10행 지속됩니다. 따라서 1000개의 8이 더 사용됩니다.
매 1000행마다 800번째 행은 8이 천의 자리수에 사용되고 그 행은 100행 지속됩니다. 따라서 1000개의 8이 더 사용됩니다.
따라서 총 4000개의 8이 사용됐구요.
1부터 10^n 까지 사용되는 8의 갯수는 n*10^(n-1) 인것 같군요.
그리고 snowall님의 알고리즘은 맞구요 ㅎㅎ
제 생각에는 맞게 나오는 것 같은데요
어디가 틀리게 될까요?
이 알고리즘을 돌리면 답이 틀릴 것 같습니다. ^^