코딩테스트/python
백준_9527_1의 개수 세기
zyin
2022. 2. 26. 22:55
문제
https://www.acmicpc.net/problem/9527
9527번: 1의 개수 세기
두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라
www.acmicpc.net
풀이
1) 패턴 파악하기
1의 자리수는 (0, 1)이 반복된다. (0이 1개, 1이 1개)
2의 자리수는 (0, 0, 1, 1)이 반복된다. (0이 2개, 1이 2개)
4의 자리수는 (0, 0, 0, 0, 1, 1, 1, 1)이 반복된다. (0이 4개, 1이 4개)
...
2**n의 자리수는 (0...., 1....)이 반복된다. (0이 2**n개, 1이 2**n개)
그룹의 절반은 0, 나머지 절반은 1로 채워져 있다.
2) 0부터 10까지 1의 개수
| 1의 자리 | (0, 1) | 그룹이 5개 | 나머지 1개 |
| 2의 자리 | (0, 0, 1, 1) | 그룹이 2개 | 나머지 3개 |
| 8의 자리 | (0, 0, 0, 0, 1, 1, 1, 1) | 그룹이 1개 | 나머지 3개 |
| 16의 자리 | (0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1) |
그룹이 0개 | 나머지 10개 |
코드
def getCount(n) :
n+=1
size = len(bin(n))-2
ans = 0
for i in range(size) :
group = 2**(i+1)
subGroup = 2**i # 그룹의 절반
div, mod = divmod(n, group) # 그룹의 수, 나머지
ans += (n-mod)//2
if subGroup < mod : # 나머지가 그룹의 절반이 넘어가면,
ans += mod-subGroup
return ans
a, b = map(int, input().split())
print(getCount(b)-getCount(a-1))