[백준 9527번] 1의 개수 세기 (Python3)

조금 당황했던 문제

 

일단 알고리즘을 찾는거 자체가 조금 까다롭다. 내가 생각한 방법은 이진법으로 1,10,100,1000,10000 등의 수 일때의 일반항을 구하고, 그 이후에는 1은 계속 켜져있으므로, 차수만큼을 뺀 후 재귀함수를 불러오는 방식이다.

 

예를 들면 이진법으로 1010인 10의 경우, 이진법 1000은 8이므로 8일때의 일반항 값을 구하고, 10-8=2에서 2만큼을 더한 뒤, 2일때의 재귀함수를 불러온다.

import sys
input = sys.stdin.readline
from collections import deque

def binary(x):
  if x < 2:
    return x
  dq = deque()
  x1 = x
  while x1>0:
    dq.append(x1%2)
    x1 //= 2
  C = len(dq)-1
  return 2**(C-1)*C+1 + (x-2**C) + binary(x-2**C)
  
a,b = map(int,input().split())

print(binary(b)-binary(a-1))

사실 당연히 시간초과가 날줄 알고, 2**C 같은걸 분할정복을 이용한 거듭제곱으로 최적화할까? 이진법 dq를 계속 가져갈까? 여러가지로 머리싸매고 고민하고 있던 와중에 일단 저장한다는 의미로 제출을 했는데 64ms로 아주 스무스하게 통과되었다...

 

 

오늘의 교훈) 뻘짓하지 말자