[java 백준]골드 5/1011번 Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static int t,x,y;
 
 
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        t=sc.nextInt();
 
 
        for(int i=0;i<t;i++){
            x=sc.nextInt();
            y=sc.nextInt();
            int distance=y-x;
            int max=(int)Math.sqrt(distance);
            
            if(max==Math.sqrt(distance)){
                System.out.println(2*max-1);
            }
            else if(distance<=max*max+max){
                System.out.println(2*max);
            }else {
                System.out.println(2*max+1);
            }
 
        }
 
 
    }
 
 
}
 
 
 
 
 
 
 
 
 
 
 
 
 

수학 문제들은 항상 규칙이 중요하다. 표로 규칙을 찾아야 문제를 풀어낼 수 있다.

 

횟수가 변하는 경계에 색깔을 줬다.

이동광년의 최대값을 max라 하면 사실상 이 값은 거리의 루트값에 int를 씌운거나 마찬가지이다. 

 

우리는 max가 값을 변할때를 기준으로 조건을 3개로 나누어 구해볼 것이다.

가장 편하게 max가 1일때를 기준으로 조건 분기를 해보자!

 

 

조건 1) max==int(Math.sqrt(distance)) 이면 2*max-1을 반환해야한다.

이 경우는 거리가  1일 때이다. 거리가 1이면 루트값이나 루트값에 int를 씌워준 것이다 똑같을 때를 의미한다.

 

 

조건 2) distance<=max*max+max

이럴 때는 횟수로 2*max를 반환해준다. 이 경우는 거리가 2일 때이다.

 

조건 3) distance>max*max+max

일때는 2*max+max를 반환해준다. 이 경우는 거리가 3일 때이다. 

 

이렇게 일반화하면 의심이 될 수도 있으니 max가 2일때도 해보자.

거리가 4일 때는 조건 1에 걸리기에 2*2-1로 횟수 3반환

거리가 5일 때는 조건 2에 걸리기에 2*2로 횟수 4반환

거리가 6일 때는 조건 2에 걸리기에 2*2로 횟수 4반환

거리가 7일 때는 조건 3에 걸리기에 2*2+1로 횟수 5반환

거리가 8일 때는 조건 3에 걸리기에 2*2+1로 횟수 5반환한다. 

 

 

도움을 받은 글

https://st-lab.tistory.com/79

[백준] 1011번 : Fly me to the Alpha Centauri - JAVA [자바]

혼자 힘으로 해내고 싶은데 항상 도움을 받는다. 더 노력해야죠...ㅜㅜㅜ