문제
1 이상의 정수를 받아서 다음의 규칙에 따른 “작업”을 반복하여 결국 1 을 만드는 게임을 하려고 한다. 아래 규칙은 한번의 작업에 대한 것이고, 작업의 결과로 만들어지는 수에 작업을 수행하는 것을 반복한다. 규칙에도 나와 있듯이 현재 수가 1 인 경우는 작업을 하지 않고 멈춘다.
- 만약 수가 1 이면 작업을 하지 않고 멈춘다.
- 만약 수가 1 이 아닌 홀수이면 1 을 더한다.
- 만약 수가 짝수이면 2 로 나눈다.
예를 들어, 받은 수가 2 인 경우는 2→1 로 1 회의 작업 후에 멈춘다. 받은 수가 4 인 경우는 4→2→1 로 2 회의 작업 후에 멈춘다. 받은 수가 3 인 경우는 3→4→2→1 로 3 회의 작업 후에 멈춘다. 받은 수가 6 인 경우는 6→3→4→2→1 로 4 회의 작업 후에 멈춘다.
앞의 예 들에서 볼 수 있듯이, 받은 수가 3 인 경우의 작업 횟수를 알면 받은 수가 6인 경우의 작업 횟수를 바로 계산할 수 있다는 것을 알 수 있다.
두 정수 N1과 N2를 입력으로 받아서 (1≤N1≤N2≤106), N1,N1+1,N1+2,…,N2의 작업 회수를 모두 더한 값을 계산하는 프로그램을 작성하라.
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다. (1≤T≤10,000) 각 테스트 케이스의 첫 줄에는 정수 N1과 N2가 주어진다. (1≤N1≤N2≤106)
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다. 그 다음 줄에, N1,N1+1,N1+2,…,N2의 작업 회수를 모두 더한 값을 출력한다.
import java.util.Scanner;
class Solution {
static int Answer;
static int[] data = new int[1000001];
static int[] total_data = new int[1000001];
static void work(int n) {
if(n%2==0) {
data[n] = data[n/2]+1;
total_data[n] = data[n] + total_data[n-1];
}
else {
data[n] = data[(n+1)/2]+2;
total_data[n] = data[n] + total_data[n-1];
}
}
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
for(int i=2; i<1000001; i++) {
work(i);
}
int T = sc.nextInt();
for(int test_case = 0; test_case < T; test_case++) {
int N1 = sc.nextInt();
int N2 = sc.nextInt();
Answer = total_data[N2] - total_data[N1-1];
System.out.println("Case #"+(test_case+1));
System.out.println(Answer);
}
}
}