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

문제

 

풀이

 

1~20까지의 수를 2^0~2^4까지의 수로 나뉘는지 체크해 본 것이다.

어떤 규칙이 있는지를 보면 9까지 1로 나눈 결과는 당연히 9다 9까지 2로 나눈 결과를 보면 당연히 4다.

체크표시를 보자 1부터 9까지의 수에 1로 나누어 지는 경우는 아홉 가지다. 1부터 9까지의 수에 2로 나누어지는 경우는 네 가지다.

이처럼 보려고 하는 숫자를 n이라고 한다면 1~n까지의 수에서 2로 나누어지는 경우는 n/2의 몫이 된다.

우리는 A~B까지의 수에서 2의 거듭제곱 꼴이면서 가장 큰 약수를 다 더하려고 한다. B까지의 약수를 다 더하고 A-1까지의 약수를 빼주면 값이 나오게 된다.

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

/**
 * 백준
 * 2로 몇 번 나누어질까
 * 골드 4
 */
public class No1407 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        System.out.println(howManyTwo(b) - howManyTwo(a-1));
    }

    private static long howManyTwo(long n) {
        long result = 0;
        long divisor = 1;  //2^0
        long beforeDivisor = 0; //이전의 divisor 담아두기


        while(true){
            long val = n / divisor;
            // 추가분만 더 해줌
            if(val > 0)result += val * (divisor - beforeDivisor);
            else break;
            beforeDivisor = divisor;    //이전 divisor
            divisor *= 2; //2의 제곱수
        }


        return result;
    }
}

 

여기서 중요한 부분은 추가분만 더해주는 것이라고 생각한다.

이미 1이 더해져 있으니 2를 더해야 하는 부분에는 1만 더해주고 4를 더해야 하는 부분에는 2만 더해준다.

이를 위해 이전의 beforeDivisor를 저장해서 사용했다.