[문제 풀이] 1 ~ n 의 정수 중 1 이 나 오 는 개수.

생각:
모든 사람 에 게 이 자 리 는 1 의 숫자 입 니 다. 예 를 들 어 숫자: 3141592, 백 자리 가 1 일 때 몇 개의 1 이 나타 납 니까?숫자 를 두 부분 으로 나 눕 니 다: pre = 31415 와 post = 92
  • 먼저 백 자리 이전, 즉 31415 xx. 백 자리 숫자 > 1 을 고려 할 때 모두 (0000 ~ 3141) 3142 * 100 개 1 이 있 습 니 다. 백 자리 숫자 < = 1 시, (0000 ~ 3140) 3141 * 100 이 있 습 니 다. 특히 여기 의 수 치 는 3141 을 얻 었 을 때 뒤의 범 위 는 더 이상 0 ~ 99 가 아니 기 때 문 입 니 다. trick 로 계산 할 수 있 습 니 다. 즉 (pre + 8) / 10 * m 예 를 들 어 여기, (31415 + 8) / / 10 * 100 = 3142 * 100 입 니 다.
  • 백 자 리 를 다시 고려 한 후에 xxxx 92 는 백 자리 숫자 가 1 일 때 만 백 자리 숫자 가 1 인 개 수 를 통계 할 수 있다. 즉, 100 ~ 192 post + 1
  • def count_1_nums(n):
    	pre = 0
    	post = 0
    	m = 1
    	counts = 0
    	while m <= n :
    		pre = n // m 
    		post = n%m
    		counts += (pre + 8) // 10 * m
    		counts += post + 1 if  pre % 10 == 1 else 0
    	return counts
    

    좋은 웹페이지 즐겨찾기