(BOJ)-1407, Python

문제 요약

출처: (BOJ)1407 - 2로 몇 번 나누어질까

두 수 $A,B$가 주어졌을 때, $A \le A+1, A+2, …, B-1 \le B$에 포함되는 모든 자연수에 대해서 각각 $n$번씩 $2$로 나눌 수 있다고 하자. $2^n$의 합을 구하는 문제이다.

• $f(15)$, $15$는 $2$로 한 번도 나누어질 수 없기에 $2^0=1$
• $f(40)$, $40$은 $2$로 세 번 나누어질 수 있기에 $2^3=8$
• $1≤A≤B≤10^{15}$

접근 과정

1. 완전탐색 접근

모든 수가 $2$로 몇 번 나누어지는지에 대한 지수 $n$을 담을 수 리스트를 생성하고, 각 지수를 계산하는 방식을 두가지 방법으로 작성했다. 그러나 아래 두 코드 각각 메모리 초과,시간 초과문제가 발생했다. 두 코드 모두 극단적인 경우인 $A=1, B= 10^{15}$에서는 당연히 문제가 발생할 것이다. 어느정도 예상됐다..

코드 구현

#지수를 계산하는 부분에서 재귀 사용(메모리 초과)
A, B = map(int, input().split())
# numList = list(i for  i in range(A, B+1))
power = [0 for _ in range(B-A+1)] #모든 수 각각의 지수를 담아놓을 리스트

def recur(number, idx): 
    if number % 2 == 0:
        power[idx] += 1
        recur(number//2, idx)
        return
    return 
answer = 0
#for idx, i in enumerate(numList):
for idx, i in enumerate(range(A, B+1)):
    recur(i, idx)
    answer += 2**power[idx]
print(answer)

#지수를 계산하는 과정에서 반복문 사용(시간 초과)
A, B = map(int, input().split())
# numList = list(i  for  i  in  range(A, B+1))

def check(number):
	idx = 0
	while number % 2 == 0:
		idx += 1
		number = number //2
	return idx
answer = 0
# for i in numList:
for	i in range(A, B+1):
	answer += 2**check(i)
print(answer)

2. 정수론 최적화

위 접근 방법으로도 안된다면, 분명 최적화할 수 있는 수학적인 방법이 있을거라고 생각했다. 그래서 규칙을 테이블을 통해 찾아보도록 했다. 다음은 $1$부터 $8$까지의 숫자에 대해 $2^n$으로 나누어질 경우를 $1$, 그렇지 않을 경우를 $0$으로 표시한 테이블이다.

	1	2	3	4	5	6	7	8
$2^0$	1	1	1	1	1	1	1	1
$2^1$	0	1	0	1	0	1	0	1
$2^2$	0	0	0	1	0	0	0	1
$2^3$	0	0	0	0	0	0	0	1

여기서 신기했던 규칙을 하나 찾을 수 있었다..!

• \[8// 2^0 = 8개\]
• \[8// 2^1 = 4개\]
• \[8// 2^2 = 2개\]
• \[8// 2^3 = 1개\]

이 몫들은 특정 자연수 $1$부터 $8$까지의 $2^n$의 약수로 포함될 수 있는 모든 수의 개수라는 것이다. 다시 말해, $8$을 $2^n$으로 나누었을 때의 몫은 $1$부터 $8$까지의 모든 수 중에서 $2^n$을 약수로 가지는 수의 개수이다!! 이를 자연수 $A$에 관한 식으로 나타낸다면 아래와 같다.

• \[(A//2) * (2-1)\]
• \[+(A//4) * (4-2)\]
• \[+(A//8) * (8-4)\]
• \[+.........\]
• \[+(A//2^n) * (2^n-2^{n-1})\]

그러면 누적합으로 계산하니 $B$를 계산한 결과에서 $A-1$의 결과를 빼면 되겠다!

코드 구현

A, B = map(int, input().split())
A -=1
tmp_A = A #2^0 = 1은 모든 자연수가 가지고 있는 수이므로 
for i in range(1, 99):
    tmp_A += (A//(2**i)) * ((2**i) - (2**(i-1)))
    
tmp_B = B
for i in range(1, 99):
    tmp_B += (B//(2**i)) * ((2**i) - (2**(i-1)))

print(tmp_B - tmp_A)  

회고

수학적 사고력을 바탕으로 접근한다는 것이 많이 어려웠고, 시간 제한, 메모리 제한으로 시간, 공간 복잡도를 어느 정도 계산하고 접근 방법을 정할 수 있는 실력까지 되게끔 더 많은 노력을 해야겠다고 깨달았다.