[백준] 1407번 2로 몇 번 나누어질까

사용 언어 - Python3

문제 -  1407번 2로 몇 번 나누어질까

1407번: 2로 몇 번 나누어질까

 

정답

최적화 - 정수론(수학) (정답 맞춘 여부 X)

모든 숫자는 1로 나누어 떨어짐 -> F(A)는 기본 최소 A이다.

2의 거듭제곱으로 나눠주면서, 최소 몇개가 2의 거듭제곱으로 나눠지는지 확인한 후 그 값만큼 더해준다.

A부터 B 구간 = B-A+1 = B-(A-1) => A에 1을 빼주고 tmp_a와 tmp_b를 계산한 후, print(tmp_b - tmp_a)

A,B = map(int,input().split())
A -= 1 # 175 !
tmp_A = 0
tmp_A += A # 1로 나누었을 때의 값 더해주기 175//1 = 175
for i in range(1,99): # 2의 배수로 나누었을 때의 값 더해주기
    tmp_A += (A//(2**i))*((2**i)-(2**(i-1)))

tmp_B = 0
tmp_B += B
for i in range(1,99):
    tmp_B += (B//(2**i))*((2**i)-(2**(i-1)))
print(tmp_B-tmp_A)

tmp_A와 tmp_B를 만드는 과정은 똑같기 때문에, 함수로 만들어도 된다.

 

레퍼런스

• 정답 깃허브

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1407_2%EB%A1%9C%EB%AA%87%EB%B2%88%EB%82%98%EB%88%84%EC%96%B4%EC%A7%88%EA%B9%8C.py