[Dev-Ping9] 백준 1011번 - Fly me to the Alpha Centauri (Java)

백준 1011번 Fly me to the Alpha Centauri

 

 

# 문제설명 

• x에서 y까지 최소한의 jump 로 가야한다.
• (0<= y-x < 2^31) 이므로, dp 배열은 선언할 수 없다.
• 배열 선언 없이 DP 의 접근방법으로 그 전의 계산을 이용하여 다음 계산을 구할 수 있으나, 최대숫자인 ( 2^31 - 1 ) 의 케이스에선 효율이 떨어질 것이 자명하다.
• 그래서 x와 y만으로 jump 횟수를 구할 수 있는 방법이 있지않을까 고민했다.

 

# 접근 방법

• 문제의 규칙에 따라, 출발과 끝은 jump 거리가 1이어야 한다.
• 즉, ( 1->2->3->2->1 ) , ( 1->2->3->3->2->2->1 ) 등으로의 jump 방식만 채택할 수 있다.
• jumpDistance[n] 을 1부터 n까지 계속 증가하고, n부터 1까지 계속 감소하는 clean하게 jump 했을시의 거리로 정의하자.

        ex) (1->2->1) , (1->2->3->2->1) ...  

• 그리고 가야할 거리가 jumpDistance[n] 를 초과하지 않는 직전의 n을 찾으면, jumpDistance[n] 의 jump를 시행 후, 남은거리를 뭐로든 채워넣으면 되지 않을까?  

 

• jumpDistance[n]을 살펴보면, 아래의 두가지 정도의 점화식을 찾을 수 있다.

 

[1번] jumpDistance[n] = jumpDistance[n-1]+ n+ n-1

[2번] jumpDistance[n] = 1*2 + 2*2 + 3*2 + ... + (n-1)*2 +  n 

 

• 이 중에서 [1번] 은 DP 방식이므로 [2번] 방식에 주목한다.
• [2번]은 공차가 2인 등차수열의 합 + n 이다.
• 공식에 따라 항을 정리하다보면 .. (n-1)(4+(n-2)*2)/2 + n = (n-1)(n) +n = n^2 에 도달한다.

 

[2번] jumpDistance[n] = n^2;

 

• 이제 남은건  jumpDistance[n] 의 jump를 시행 후 남은 거리를 어떻게 핸들링 하느냐만 남았다.
• 특정한 케이스를 하나 잡아 생각하고, 일반화 시키는게 빠르다.

 

jumpDistance[3] 을 시행하면 1, 2, 3, 2, 1 의 점프를 한다. 

 

남은거리가 예를 들어 4라고 한다면, 최소의 점프를 하려면 (3, 1) 또는 (2, 2) 가 될 것이다.

 

당연히 최소의 점프를 해야하니, 큰 수의 점프를 최대한 시행하는게 맞을 것이다.

 

jumpDistance[n] 의 최대 점프거리는 n이다.

 

남은거리를 n으로 계속 빼준 후, n보다 작은거리가 남으면 그 만큼만 jump해주면 최소의 jump가 아닌가...!

 

즉, 남은거리/n 을 한 후, 나머지가 있다면 1번의 jump를 더 수행한다.

 

• 문제 해결에 필요한 로직을 정의 했으니, 구현만 하면 끝이다. 🥰

 

---

# 코드 구현

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

public class Main{

    static int minJumpCal(int leftDistance, int n){
        int cnt = 0;
        if(leftDistance>=n){
            cnt=leftDistance/n;
        }
        if(leftDistance%n == 0) return cnt;
        else return cnt+1; // Max Dis jump 로 cnt 번 진행한 후, 나머지 만큼 1번진행 
    }
    public static void main(String[] args) throws IOException{
    	// System.out.println((long)Math.sqrt(Math.pow(2,31)));
        // System.out.println((int)Math.floor(Math.sqrt(35)));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int times = Integer.parseInt(br.readLine());
        
        StringTokenizer st;
        
        for(int i=0; i<times; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            // capable : 1, 2, 3, 4, 5 ...
            // last jump should be 1. (it means before last should be 2)
            // example : 1, 2, 3, 2 ,1 
            // return : how many jumps needed
            // y-x = diff < 2^31 (=int)
            // jump[n] : (1,2,...,n,...,2,1)
            // 근데 jump를 1 2 3 4 3 3 2 1 로... 할수도있지않나?
            // jump[1]= 1; jump[2]=4; jump[3]=9; jump[4]= 16; 
            // jump[n]= jump[n-1]+ n+ n-1; 
            // jump[n]= (n-1)(4+(n-2)*2)/2 + n = (n-1)(n) +n = n^2 // ...!!!!!!!!!!!
            // jump-cnt[1]=1; jump_cnt[2]=3; jump_cnt[3]=5; 
            // jump-cnt[n]=2n-1
            // diff>n^2 : sqrt
            
            int diff = end - start;
            int n = (int)Math.floor(Math.sqrt(diff)); // if 2^31? it's working.
            int jumpDistance = (int)Math.pow(n,2);    // no overflow? yes
            int jumpCnt = 2*n -1;                     // no overflow too, cuz pow working.
            int leftDistance = diff - jumpDistance;
            int minJump= minJumpCal(leftDistance,n);
            System.out.println(jumpCnt+minJump); // total jump count
        }
    }
}