[백준 9527] 1의 개수 세기

9527번: 1의 개수 세기

알고리즘 : 수학

난이도 : 골드Ⅱ

 

1. 문제요약

• $10^{16}$ 이하의 두 자연수 A, B가 주어진다.
• A이상 B이하의 모든 수를 이진수로 표현할때 1의 개수를 출력한다.

2. 아이디어

• A,B의 범위가 매우 크기 때문에 단순하게 접근하면 시간 및 메모리제한에 걸리게 된다.
• 문제풀이전략을 고민할때에는 작은 문제부터 생각하면서 접근하면 좋다.
• 우선 이진수 1000에 대해 생각해보자.
  • 1부터 1000까지의 이진수는 1, 10, 11, 100, 101, 110, 111, 1000이고 1의 개수는 총 13이다.
  • 여기서 맨 왼쪽 자리수를 제외하고 생각해보면, 모든 자리수에서 1이 4번씩 등장하고 있다.
  • 즉 맨 왼쪽 자리를 제외한 총 세개의 자리에서 1이 4번씩 등장하기에, 4 * 3 + 1 = 13이 되는 것이다.
  • 여기에 더하여, 왜 1이 4번씩 등장하는지도 알 수 있다. 세개의 자리에서 계산하기 때문에, 각 자리수의 1은 해당 자리수를 제외한 나머지 두개의 자리에 대하여 두번씩 등장할 수 있기 때문이다.
  • 정리하면, 1000같은 이진수는 맨 처음 1을 제외한 자리수를 x라 할때, $2^{x-1}*x +1$만큼의 1이 나오게 된다.
• 다음으로, 이진수 101100에 대해 생각해보자.
  • 101100은 1) 1부터 100000, 2) 100001부터 101000, 3) 101001부터 101100 총 3단계로 나누어 생각할 수 있다.
  • 우선 1)에서는  위에서 구한 공식에 따라 100000까지의 1의 개수를 구하면 된다.
  • 2)에서는 1000까지의 1의 개수를 구하고, 1000까지의 모든 수에 대하여 앞에 10이 붙어 있으므로 이진수 1000까지의 개수인 $2^3=8$을 더 더해주면 된다. (개수 8 또한 세개의 자리수라는 점에서 얻어진다)
  • 3)에서도 마찬가지로 100까지의 1의 개수를 구하고 이진수 100까지의 개수인 4에 앞에 붙어있는 101의 1의 개수 2를 곱한 8을 더 더해주면 된다.
  • 정리하면, 101100과 같은 일반적인 이진수의 경우 각 자리수의 1을 기준으로 답을 구해주면 된다. 예를들면 101100에서 볼드체 처리한 중간의 1을 기준으로 생각할때, 왼쪽의 1의 개수인 1에 $2^3$을 곱하여 8이 되고, 오른쪽의 자리수가 세자리이므로 $2^{3-1}*3+1 =13$이 된다. 즉, 100001부터 101000까지의 1의 개수는 8+13=21이다.
• 결국, 이진수로 변환시킨후 for문으로 순회하면서 1인 경우에 대하여 위에서 구한 공식에 따라 개수를 카운팅해주면 답을 얻을 수 있음을 알 수 있다.

3. 구현과정

• n이하의 모든 이진수에 대해 1의 개수를 세는 함수인 countone(n)을 정의하자.
• bin(n)[2:] 으로 주어진 자연수 n을 이진수로 고친다. 이 경우 문자열로 표현됨에 유의한다.
• 이진수로 표현한 nn에 대해 nn의 길이를 length에 저장한다. 이외에 현재 자리수 기준 왼쪽의 1의 개수를 세는 변수인 checkone과 정답을 저장할 answer 변수도 각각 선언한다.
• 이제 nn의 각자리수를 앞쪽부터 순회한다. 값이 1인 자리수에 대하여 위에서 고안한 수식에 따라 answer를 업데이트 하고, checkone에도 1을 더해준다.
• for문을 다 순회하면 맨 마지막 자리만이 남는다. 맨 마지막 자리가 1인 경우에는 checkone의 값에 1을 더한 값을 answer에 더해주어야 한다.
• 이 answer값이 구하는 n이하의 이진수의 모든 1의 개수를 센 값이므로 위 함수는 answer를 return해주면 된다.
• 마지막으로 a와 b값을 입력받고 countone(b) - countone(a-1)을 출력하면, a이상 b이하의 모든 자연수를 이진수로 표현한 경우에 1의 개수가 된다.

4. 파이썬 코드

# n이하의 모든 이진수에 있는 1의 개수를 세는 함수
def countone(n):
    nn = bin(n)[2:]
    length = len(nn)
    checkone = 0  # 현재 자리수 기준 왼쪽의 1의 개수
    answer = 0
    for i in range(length - 1):
        if nn[i] == '1':
            tmp = length - i - 1  # 현재 자리수 기준 오른쪽의 자리수
            answer += checkone * 2 ** tmp + tmp * 2 ** (tmp - 1) + 1
            checkone += 1
    answer += (checkone + 1) * int(nn[length - 1])  # 맨 마지막 자리가 1인 경우
    return answer

a, b = map(int, input().split())
print(countone(b) - countone(a - 1))