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

문제

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

 

 

접근 방법

1. 상당히 애를 먹었던 문제였다. f(n) 정의가 주어지고 a b 자연수가 주어졌을때 f(a)~f(b)를 구하는 문제이다.
2. 먼저 2로 한번도 나눌수 없는 개수를 더하고
3. 2로 나누어지지만 단 한번만 나누어지는 갯수, 2^2로 나누어지지만 단 한번만 나누어지는 갯수, 2^3...2^4 로나누어지지만 단 한번만 나누어지는 갯수를 더해주었다.

아마 위의 접근 방법만 보면 이해가 안될것이다. 예를들어서 먼저 B값이 10 이라고 가정을 해보자. 2번 과정을 해보면

10개중 2로 나누어지지 않는 값은 n/2 = 5 개가 될 것이다.

f(1) = 2^0

f(2) = 2^1

f(3) = 2^0

f(4) = 2^2

f(5) = 2^0

f(6) = 2^1

f(7) = 2^0

f(8) = 2^3

f(9) = 2^0

f(10) = 2^1

-> 5개

=> 10/2 *1 => 5

 

그럼 이 5개를 제외한 값중 2로 단 한번만 나누어 지는 수들은 어떻게 구할까

f(2) = 2^1

f(4) = 2^2

f(6) = 2^1

f(8) = 2^3

f(10) = 2^1

-> 3개

5/2+1 * 2 = > 6

 

그럼 나머지 2개중 4로 단 한번만 나누어지는 수들은

f(4) = 2^2

f(8) = 2^3

->1개

2/2*4 => 4

 

이런식으로 구하면 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader br;
    private static StringTokenizer st;
    private static long A,B;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());
    }
    public static long total(long n){
        long ans = 0;
        long temp = 1;
        
        while(n != 0){
            if(n%2!=0){
                ans+=((n/2)+1)*temp;
            }else{
                ans+=(n/2)*temp;
            }

            temp*=2;
            n/=2;
        }
        return ans;
    }

    //실행
    public static void process() {
        System.out.println(total(B)-total(A-1));
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}