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

문제

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

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

 

 

풀이방법

범위가 (1≤A≤B≤10^15) 로, 엄청나기 때문에 숫자 하나 하나 나누면서 계산을 할 수 없다고 생각했다.

그래서 생각해낸 방법이 1~B 까지 더한값에 1~A-1 까지 더한 값을 빼면, 즉 f(B) - f(A-1) 으로 계산하는 방법을 생각했다.

function 안에서는 일정한 규칙을 찾았고, 그 규칙에 따라 계산해 주면 된다.

 

규칙은주어진 숫자 n에 대해서 n/2 개가 홀수이고나머지 n/2개에 대해서 (n/2)/2 개가 2로 나누어떨어지고

나머지 (n/2)/2 개에 대해서 ((n/2)/2)/2 개가 2로 나누어떨어지고 ... 이런 규칙을 갖고있다.

코드로 이런 규칙을 정리해보면 아래와 같다.

 

소스코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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(calc(B)-calc(A-1));

    }
    static long calc(long num) {
        //2로 몇 번 나누어지는지 구하는 함수
        long sum = 0;
        long temp = 0;
        long ex = 1; //지수
        while(num != 0) {
            if(num %2 == 0) {
                temp = num/2;
            }else {
                temp = num/2 +1;
            }
            sum += temp * ex;
            ex *= 2;
            num -= temp;

        }
        return sum;
    }

}

결과