백준 1011번 : Fly me to the Alpha Centauri (JAVA) 문제 풀이

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

---

 

 

이 문제는 정말 어려웠다.. 결국 인터넷에 풀이를 검색해서 찾아봤다 ㅠ.........

일단 규칙을 찾기 위해서 표를 한번 그려보자.

distance  = y - x

move = 모든 이동 거리

count = 총 이동 횟수

max  = 이동 거리 중 최대 이동 거리

위에 표를 보면 세가지 규칙을 알 수 있다.

1. max 가 변하는 시점에 distance는 max의 제곱이 된다.
2. max가 변하는 시점에 count는 max * 2 - 1이 된다.
3. max가 변한 시점부터 count가 max개씩 분리되어 count가 같게 된다. (이 부분은 아래에서 자세히 설명하겠다.)

 

규칙 1.

// distance = max * max ;
int max = (int) Math.sqrt(distance);

 

규칙 2.

// max가 distance의 제곱근일 경우
if( max == Math.sqrt(distance) ){
	count = max * 2 - 1;
}

 

규칙 3.

위에 표는 그린 표의 일부분을 잘라온 부분이다.

max가 변한 시점인 9 부터 다음으로 변하는 시점인 16까지의 사이에 있는 개수가 max*2개 가 된다.

max가 변한 시점이후로 max개는 count가 max * 2가 되고,

그 이후로 max개는 count가 max * 2 + 1이 된다.

 

그럼 우리는 count를 이렇게 구할 수 있다.

// max * max < distance <= max*max + max --> max*2
// max*max + max < distance  --> max*2 + 1

if( distance <= max * max + max ){
	count = max * 2;
} else {
	count = max * 2 + 1;
}

 

 

 

 

나의 풀이

package Baekjoon;

import java.io.*;
import java.util.StringTokenizer;

public class Alpha_Centauri {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        long X;
        long Y;
        long distance; // 행성 간 거리
        long max;
        long count = 0;

        int T = Integer.parseInt(bf.readLine());

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(bf.readLine());
            X = Integer.parseInt(st.nextToken());
            Y = Integer.parseInt(st.nextToken());
            distance = Y - X; // 거리 계산
            max = (int)Math.sqrt(distance); // max 구하기

            if (max == Math.sqrt(distance)) {
                count = max * 2 - 1;
            }else{
                if (distance <= max*max + max) {
                    count = max * 2;
                }else {
                    count = max * 2 + 1;
                }
            }
            bw.write(count + "\n");
        }
        bw.flush();
        bw.close();
    }
}