[Baekjoon] 백준 1011: Fly me to the Alpha Centauri - Java

문제

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

 

풀이

시작지점과 도착지점이 도달할때, 반드시 1광년으로 해야한다고 했고, 공간 이동 장치 횟수의 최솟값을 도출해야한다.

 

거리 - (광년이동)

1 - (1)

2 - (1 1)

3 - (1 1 1)

4 - (1 2 1)

5 - (1 2 1 1)

6 - (1 2 2 1)

...

9 - (1 2 3 2 1)

...

12 - (1 2 3 3 2 1)

...

16 - (1 2 3 4 3 2 1)

...

20 - (1 2 3 4 4 3 2 1)

 

그러면 거리에 따른 이제 공간 이동 장치 작동 횟수를 보도록 하겠다. 개수는 작동 횟수에 해당하는 종류의 개수를 뜻한다. 예를 들어, 3 ~ 4에 해당하는 거리(거리 개수)는 3번 작동(작동 횟수)해야하며, 3번 작동해야하는 거리의 개수(종류)는 2가지이다.

거리	1	2	4	6	9	12	16	20
거리개수	1	1	2	2	3	3	4	4
작동 횟수	1	2	3	4	5	6	7	8

 

자 그러면, 거리가 제곱수를 기준으로 빨간색을 주목하면 패턴이 보인다. 

우리는 거리에 해당하는 거리개수만 구하면 작동 횟수를 구할 수 있다. 그러면 어떻게 구할 수 있을까? 시그마 공식을 사용한다. 

 

우리가 1부터 10까지 더한 값은 55라고 알고 있다. 시그마 공식으로 어떻게 도출이 되는가.

1부터 k까지 더한 값은 k * (k + 1) / 2이다. 그래서 k = 10 => 55가 나오게 된다.

 

표에서 거리의 개수를 보면 1 1 2 2 즉 2개씩 더하고 있다. 즉, (k * (k + 1) / 2) * 2이므로, k * (k + 1)이다.

k = 1이면, 거리 : 2

k = 2이면, 거리 : 6

k = 3이면, 거리 : 12

k = 4이면, 거리 : 20

 

그러면 y - x(거리)에 해당하는 k값을 구한다.

k^2보다 같거나 작다면 (2 * k) - 1이고,

그게 아니라면 (2 * k)이다.

 

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        
        for (int test = 1; test <= t; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            
            //이동거리
            long dist = y - x;
            
            long k = 1;
            
            //k를 구하기
            while (true) {
                if (k * (k + 1) >= dist) {
                    break;
                }
                
                k += 1;
            }
            
            //공간 이동 장치 작동 횟수의 최솟값
            long answer = -1;
            
            if (dist > (k * k)) {
                answer = 2 * k;
            }
            else {
                answer = (2 * k) - 1;
            }
            
            sb.append(answer).append("\n");
        }
        
        //출력
        System.out.print(sb);
        
        br.close();
    }
}