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

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

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

 

풀이

$$S(n)=\sum_{i=0}^{n} f(i)$$

라 합시다(f(0)은 아무 값이나 상관없지만 저는 그냥 0으로 두었습니다). 문제에서 구하라 하는 값인 $f(A)+f(A+1)+\cdots+f(B-1)+f(B)$는 $S(B)-S(A-1)$로 나타낼 수 있습니다.

그러면 S(n)값은 어떻게 구하면 좋을까요?

f(n)은 n이 홀수라면 무조건 1이 나옵니다. 그리고 n=2k라면, f(n)=2f(k)로 바꿀 수 있게 됩니다. 

이를 활용해서 S(n)을 n이 홀수일 때와 짝수일 때를 나누어서 풀어봅시다.

 

n이 홀수일 때(n=2k+1), n 이하의 홀수들의 f값의 합은 k+1이 됩니다. 이는 n/2+1로 나타낼 수 있습니다. n 이하의 짝수들의 f값의 합은 $f(2)+f(4)+\cdots+f(2k-2)+f(2k)=2f(1)+2f(2)+\cdots+2f(k-1)+2f(k)=2S(k)$가 됩니다. k=n/2이므로 정리해보면 $S(n)=n/2+S(n/2)+1$이 됩니다.

n이 짝수일 때(n=2k), n 이하 홀수들의 f값의 합은 k가 됩니다. n 이하의 짝수들의 f값의 합은 2S(k)가 됩니다. 따라서 $S(n)=n/2+S(n/2)$가 됩니다.

 

이것을 가지고 재귀함수로 표현했을 때, 시간복잡도는 $O(logAB)$가 됩니다.

 

코드

위의 풀이로 짠 코드입니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum(ll a) {
    if(a==0) return 0;
    if(a==1) return 1;
    if(a%2) return a/2+2*sum(a/2)+1;
    else return a/2+2*sum(a/2);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << sum(b)-sum(a-1);
}

 

감사합니다.