백준 1407 2로 몇 번 나누어질까 파이썬 문제풀이 (python 정수론 최적화)

문제 보러가기

 

백준 2로 몇 번 나누어질까 파이썬 문제풀이

함수 f(x)가 있다.

2로 나눠지는 몫을 지수로한 2의 거듭제곱을 구하는 함수이다.

 

무슨 말이냐면

15와 같이 2로 0번 나눠지면

2^0 = 1

 

12와 같이 2로 2번 나눠지면

2^2 = 4

인 함수이다.

 

A, B가 주어지고 B는 항상 A이상의 값이다.

A~B까지의 자연수 하나하나를 위 함수 f(x)에 넣은 값을 모두 더하는 문제이다.

$$f(A) + f(A+1) + ... + f(B-1) + f(B)$$

 

일단 구현하기

문제가 상당히 헷갈린다. 

일단 말 그대로 f함수를 구현하고, 

A~B까지의 수에 대해서 f함수를 실행해보자.

 

시간 초과가 예상되긴 하지만.. 달리 방법을 모르겠다.

A,B = map(int,(input()).split())
ans = 0
def f(n):
    cnt = 0
    while n%2 == 0:
        n//=2
        cnt+=1
    return 2**cnt

for i in range(A, B+1):
    ans += f(i)
print(ans)

 

예상대로 시간 초과..

어떻게 접근해야할까.

 

정수론 방법

정말 새로운 방법을 여기서 이용해야한다.

정수론을 공부해보았다면 들어봤을 수 있지만,

 

직관적으로 떠오르기 힘들기에 이 방법은 따로 외우는 게 좋을 것 같다.

 

수 N을 \(2^1, 2^2, 2^3 ...\) 로 나눈 몫의 총합

이게 무슨 말일까?

 

20이라는 수를 갖고 생각해보자.

문제에서 1, 20이 입력으로 들어온다면 1~20까지 모든 수의 f함수 값을 더하는 것이다.

 

직접 하나하나 구해보면 18이라는 값이 나오게 되는데,

신기하게도 이걸 쉽게 구하는 방법이 있다.

 

20을

2로 나누면 정수 몫은 10

4로 나누면 정수 몫은 5

8로 나누면 정수 몫은 2

16으로 나누면 정수 몫은 1

 

그 이상의 2의 거듭제곱수로는 나눠지지 않는다.

이걸 모두 합하면 18이 나온다.

 

...!

 

즉 이 법칙을 이용하면 A, B 입력에 대해서 

20으로 했던 과정을 B에 해주고, A에 해주고 차를 구하면 답이 나온다는 말이다!

 

아 사실 답이 나오는 건 아니다.

새로 알게된 위 방법으로 f(x)를 구하려면, 

x에 대한 값과 x-1에 대한 값을 구해서 빼주어야한다.

 

20의 경우 18이라고 했다.

20-1 = 19에 대해서 새로운 방법을 적용하면 16이다.

20에 대한 값과 19에 대한 값을 빼면 18-16 = 2이다.

 

이렇게 f(20)=2를 구할 수 있다.

이걸 A~B까지 각각 해주면 된다.

 

주의할 점은 f(1) = 0의 예외만 지켜주면 구현할 수 있겠다.

구현하기

A,B = map(int,(input()).split())
ans = 0

def magic(n):
    i=1
    res = 0
    while 2**i <= n:
        res += n//(2**i)
        i+=1
    return res

for i in range(A,B+1):
    if i == 1:
        ans+=(2**0)
    else:
        magicVal = magic(i) - magic(i-1)
        ans+=2**magicVal
print(ans)

흠... 이래도 시간 초과가 생긴다. 

아무래도 저 while문 조차도 줄이는 방법이 있는 모양이다.

 

다른 방법 

보아하니 시간초과가 나는 이유는 A~B까지 일일이 진행했기 때문이다.

즉 역으로 생각하면 B차례에서 뭘 빼면 f(A)~f(B)까지 합이 나오거나 하는 규칙이 숨어있다는 것이다.

 

위에서 내가 놓친 점을 생각해보면

f(B)를 구하기 위해서

1~B까지 2로 나눠지는 개수 (위의 정수론 방법)에서

1~(B-1)까지를 뺐었다.

 

이거 다항식을 생각해보면, 

정수론 방법으로 B - (A-1)를 하면 A~B 범위까지의 2로 나눠지는 개수를 구할 수 있다. 

 

여기서 위에서 잘못 한 이유가

중간중간에 2로 나눠지지 않으면 1을 더해야하기 때문이었다.

 

그러면 어차피 2로 나눠지지 않는다는게 홀수라는 뜻인데

홀수의 개수만큼 1을 더해주면 되는거 아닌가?

 

정리하자면, 

정수론 방법(B) - (A-1)을 하고 거기에 A~B 범위의 홀수의 개수를 더해주면 된다.

 

... 아아 이 방법도 아니다. 엄밀히 말하면 f함수는 2로 나눠지는 갯수를 2의 거듭제곱으로한 값이다.

하지만

"이거 다항식을 생각해보면, 

정수론 방법으로 B - (A-1)를 하면 A~B 범위까지의 2로 나눠지는 개수를 구할 수 있다. "

이 접근법은 유효하다

 

f함수를 잘 보면 홀수는 고려하지 않아도 1이 기본으로 깔려있고,

2의 배수가 몇 개 있는지를 세면 된다.

 

B와 A-1에서 각각 2의 제곱수들을 차례로 나눠보면, 

1~B까지 범위, 1~(A-1) 범위까지 2의 제곱수가 몇 개 있는지 알 수 있다. 

 

그걸 다 더해주고 자기자신을 더하면 1~N까지 숫자의 f함수 합이 구해진다.

이걸 빼주면 된다.

 

코드로 살펴보자.

정답 코드 

A,B = map(int,(input()).split())
def magic(n):
    res = n
    i=2
    while i <= n:
        res += (n//i)*(i//2)
        i*=2
    return res

print(magic(B) - magic(A-1))

중요한 것은 (n//i)*(i//2) 부분이다

 

i는 2의 거듭제곱을 하나씩 확인하는 것

n//i는 2의 거듭제곱들이 n까지 총 몇 개 들어있는지

 

i//2는 2의 거듭제곱에서 지수를 -1 한 것인데

이는 기본적으로 1을 가지고 시작하기 때문에 엄밀히 말하면 증가량이다

 

무슨 말이냐면

1에서 2로는 1증가

2에서 4로는 2증가

4에서 8로는 4증가

이런식으로 2 거듭제곱의 단계가 1씩 낮아지는 것을 의미한다.

 

여기서 f(x)함수는 n//i에 해당한다고 보면 된다. 

n까지의 모든 f(x)값을 더한 셈.

 

후우.. 이번 문제는 이해하기 너무 어려웠다.