[Codeground] SCPC 5회 예선 : 오르락 내리락

문제 : 다음 규칙에 따라 숫자를 1로 만드는 게임이다.

 

1. 수가 1이라면 종료

2. 1번 이후 홀수라면 1을 더한다.

3. 2번 이후 짝수라면 2로 나누고 처음으로 돌아간다.

 

입력	출력
1 ≤ T(테스트 개수) ≤ 10000 1 ≤ N1 ≤ N2 ≤ 1000000	N1부터 N2까지 각각 필요한 횟수의 총합

 

 

JAVA

언어	결과	수행시간	메모리	점수
Java	Pass	0.12642	208304	100

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

public class Solution {

	static int[] list = new int[1000001]; //개별횟수
	static int[] slist = new int[1000001]; //구간합
	static int a,b;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n,i;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());//테스트 개수
		list[2] = 1;
		for(i=2;i<=1000000;i++) {//2~1000000 까지 구간합 미리 계산
			slist[i]=slist[i-1]+make1(i);
		}
		for(i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());//N1
			b = Integer.parseInt(st.nextToken());//N2
			sb.append("Case #"+i+"\n"+(slist[b]-slist[a-1])+"\n");
		}
		System.out.println(sb.toString()); //출력
		br.close();
	}
	static int make1(int k) {
		if(list[k]!=0) {//이미 저장된 값이라면 출력후 리턴
			return list[k];
		}else if(k%2==0) {
			return list[k] = 1 + make1(k>>1); // 짝수라면 2로 나눈다
		}else {
			return list[k] = 1 + make1(k+1); // 홀수라면 1을 더한다
		}
	}
}