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

 

상당히 애를 먹었던 문제

 

이 문제는 크로아티에서 고등학생 대상으로 나온 문제다.

상당히 애를 먹었던 문제다.(아직 멀었나 보다)

 

코드 먼저 살펴보자

a,b = map(int, input().split())

def calc(number) :
  if number == 0 :
    return 0
  elif number == 1 :
    return 1 
  elif number % 2 == 0 :
    return number // 2 + 2 * calc(number // 2)
  elif number % 2 == 1 :
    return number // 2 + 2 * calc(number // 2) + 1

print(calc(b) - calc(a-1))

애를 먹었던 거에 비해서는 굉장히 간단하다. 

규칙만 잘 찾으면 절대 어렵지 않은 문제다.

그 규칙에 대해서 아래 필기로 같이 살펴보자

점화식 설명 내용

 

1. f(홀수)는 무조건 1이다
2. f(짝수)는 f(짝수/2)의 2배다 (f(2) == 2, f(4) == 4, f(6) == 2 * f(3))
3. 입력받은 a에서 b까지의 각 숫자들을 나눌수 있는 숫자들중 2의 거듭제곱에 해당하는 가장 큰수 들의 합이다. 
   (숫자의 범위들을 살펴보자 0 <= a, b <= 10^15 => 순회 잘못걸리면 2초안에 못들어온다) => 범위를 탐색하는 것이 아니다.
4. s(n)은 f(1) + f(2) + .... + f(n-1) + f(n) 의 값이다. 3번의 정의를 s(b) - s(a-1)로 바꾸면??? => 문제에서 요구하는 것과 같다.
5. n이 짝수면 s(n)의 절반은 1이다(절반은 홀수니까), n이 홀수면 s(n)의 절반 + 1 은 1이다
6. 절반의 1을 뺀 나머지는 전부 짝수다 f(2n) = 2 * f(n)이므로 점화식 설명 내용 이미지의 그림 처럼 짝수들만 더한 값은 
   f(2) + f(4) + f(6) + ..... +  f(2n-2) + f(2n) = 2f(1) + 2f(2) + 2f(3) + ..... + 2f(n-1) + 2f(n) = 2s(n) 이다
7. n이 짝수 s(n) = n / 2 + s(n/2),  n이 홀수 s(n) = n / 2 + s(n/2) + 1 이 되게 된다.
8. 7번의 내용을 재귀함수로 만들면 끝!

 

 

 

출처: https://www.acmicpc.net/problem/1407

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