BOJ_17613_점프 (Java)

[Platinum II] 점프 - 17613

문제 링크

성능 요약

메모리: 21952 KB, 시간: 212 ms

분류

분할 정복, 다이나믹 프로그래밍

제출 일자

2025년 2월 10일 12:07:56

문제 설명

개구리가 수직선 위의 0에서 출발해서 오른쪽(x좌표가 증가하는 방향)으로 점프들을 수행한 후 어떤 수 x > 0에 도착하려 한다. 이 때, 점프 간격은 1로부터 시작해서 항상 직전 점프한 간격의 2배로 증가해야 한다.

만일 점프간격을 2배씩 계속 증가시켜 마지막 점프에서 목표 수 x를 지나칠 것 같으면, 필요한 경우 언제든지 점프 간격을 다시 처음 상태인 간격 1로 되돌아 갈 수 있다. 이것을 재시작이라고 부른다. 예를 들어, 아래 <그림 1>과 같이 x = 19에 도달하기 위해서 2번의 재시작을 수행해서 (1+2+4+8)+(1+2)+(1)= 19 와 같이 7번의 점프로 도착할 수 있다.

<그림 1>

개구리가 0에서 출발해서 어떤 양의 정수 N에 도달하기 위한 점프 횟수의 최솟값을 J(N)으로 나타내고 N의 점프넘버라고 부를 것이다. 예를 들어, <그림 1>을 보면 J(1) = 1, J(3) = 2, J(7) = 3, J(15) = 4, J(16) = 5, J(18) = 6, J(19) = 7과 같음을 알 수 있다.

여러분은 어떤 특정 구간 [x, y]안의 수들의 점프넘버들 중 최댓값을 찾아서 출력한다. 즉, 아래 조건을 만족하는 w를 찾아서 출력한다.

w = max{J(i) | x ≤ i ≤ y}

입력

첫 번째 줄에는 여러분에게 주어질 구간의 개수 T가 주어진다.(1 ≤ T ≤ 2,000) 이후 T개의 줄에 대해 답을 구해야 할 구간을 나타내는 두 정수 x, y가 공백을 사이에 두고 주어진다 (1 ≤ x ≤ y ≤ 10⁹).

출력

T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 번째 줄에 출력되는 정답은 첫 번째로 주어지는 구간에 대응되어야 한다.

문제 풀이

아이디어는 겨우 떠올렸는데 분기가 어려웠다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;
public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int TC;
    static long X, Y;
    static long[] arr;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_17613_점프/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        TC = Integer.parseInt(br.readLine());
        // int 가 2^31-1까지니까 최대 31번점프가능
        arr = new long[31];
        for(int i=1; i<31; i++) {
            arr[i] = (1L << i) -1;
        }
        while(TC-->0){
            st = new StringTokenizer(br.readLine());
            X = Long.parseLong(st.nextToken());
            Y = Long.parseLong(st.nextToken());
            sb.append(maxJ(X, Y)).append('\n');
        }
        System.out.println(sb);
        bw.flush();
        bw.close();
        br.close();
    }
    // x까지 최소점프횟수
    private static int calJ(long x) {
        long tmp = 1;
        int j = 0;
        while (x>0) {
            x -= tmp;
            // 점프초기화
            if (2 * tmp > x) tmp = 1;
            else tmp *= 2;
            j++;
        }
        return j;
    }
    // [left ~ right] 최대점프횟수구하기
    private static int maxJ(long left, long right) {
        if(left == right) return calJ(right);
        if(left + 1 == right) return Math.max(calJ(left), calJ(right));
        // right보다 큰 2거듭제곱 J찾기
        int idx;
        for(idx=0; idx<31; idx++){
            if(arr[idx] > right) break;
        }
        if(idx==1) return 1;
        //J(i-1), J(i-2)
        long J_1 = arr[idx-1]; // J(i-1)
        long J_2 = arr[idx-2]; // J(i-2)
        // case1: 20~100 (left <= J2 인 경우)
        // J2까지 가는 경우와 J1까지 가는 경우 중 더 큰 값 선택
        if(left <= J_2) return Math.max((idx-2) + maxJ(0, J_2), (idx-1) + maxJ(0, right-J_1));
        // case4: 64~100 (left > J1 인 경우)
        // 예: [64~100] 구간처럼 시작점이 J1보다 큰 경우
        // 전체 구간을 J1만큼 빼서 재귀적으로 처리
        if(left > J_1) return (idx-1) + maxJ(left-J_1, right-J_1);
        // case3: 40~100 (J2 < left < J1 인 경우)
        // 예: [32~62] 구간처럼 시작점이 J2와 J1 사이인 경우
        // J2를 밟고 가는 경우와 J1까지 가는 경우 중 더 큰 값 선택
        if(left < J_1) return Math.max((idx-2) + maxJ(left-J_2, J_2), (idx-1) + maxJ(0, right-J_1));
        // case2: (left == J1 인 경우)
        // 예: [63~100] 구간처럼 시작점이 정확히 J1인 경우
        // J1까지는 idx-1번의 점프로 도달, 나머지는 재귀로 처리
        return (idx-1) + maxJ(0, right-J_1);
    }
}