[JAVA] 백준 1011번 Fly me to the Alpha Centauri : 부등식과 반복문 3

1011번: Fly me to the Alpha Centauri

 

 

1. 문제 추상화 

 

장치를 한 번 작동시킬 때, 이전 속도보다 1 증가, 유지, 1 감소가 가능할 때, X지점에서 Y 지점까지 장치를 최소한으로 몇 번 작동해야 도착할 수 있는가? ( 단, 처음과 끝의 속도는 1광년이다. )

 

2. 알고리즘

 

개인적으로 어려웠다.

이런 수열 문제는 귀찮더라도 0부터 하나씩 수를 나열하며 규칙을 찾는 것이 정도(正道)이다. 이런 노력없이 대충 문제의 조건으로만 규칙성을 찾으려 한다면 요행을 바라는 것이다.

 

우주선은 1광년을 가려면 1을 추가해야한다. 

 

▷ 4광년 : 1 - 2 - 1

▷ 5광년 : 1 - 2 - 1 - 1

 

5광년을 1 - 3 - 1로 가면 안 된다. 우주선은  1 증가, 유지, 1 감소만 가능하다. 1광년을 더 가보자.

 

▷ 5광년 : 1 - 2 - 1 - 1

▷ 6광년 : 1 - 2 - 2 - 1

 

장치 작동 최소화를 위해, 1 - 2 - 1 - 1 - 1이 아닌, 1 - 2 - 2 - 1로 움직인다. 1광년을 더 가보자.

 

▷ 6광년 : 1 - 2 - 2 - 1

▷ 7광년 : 1 - 2 - 2 - 1 - 1

 

6광년의 횟수를 유지한 채, 어느 한 곳을 1 증가시키면 조건에 부합하지 않는다. 그러므로 장치 작동횟수를 늘려준다. 여기에는 규칙이 있다. 1을 오른쪽 끝에 추가 한 후, 1광년을 지날 때마다 오른쪽부터 1씩 증가시면 된다. 그러다 1 - 2 - 1 나 1 - 2 - 2 - 1와 같이 대칭을 이루면 끝에 다시 1을 추가한다. 이 규칙을 따라서 표를 작성해보자. 

 

거리	이동패턴	작동횟수
2	11	2
3	111	3
4	121	3
5	1211	4
6	1221	4
7	12211	5
8	12221	5
9	12321	5
10	123211	6
11	123221	6
12	123321	6
13	1233211	7
14	1233221	7
15	1233321	7
16	1234321	7
17	12343211	8

 

우리의 목적은 작동횟수를 찾는 것이다. 그러므로 작동횟수의 규칙을 찾아보자. 앞서 확인했듯이, 1광년씩 증가할 때마다 일정한 패턴으로 이동한다. 그러므로 작동횟수도 일정한 특징을 갖는다. 

 

작동 횟수	거리
2	2 (1개)
3	3, 4 (2개)
4	5, 6 (2개)
5	7, 8, 9 (3개)
6	10, 11, 12 (3개)
7	13, 14, 15, 16 (4개)
8	17, 18, 19, 20 (4개)

 

우리의 목적은 특정 거리가 입력되었을 때, 작동횟수를 구하는 것이다. 표를 보면 알 수 있듯이, 거리는 어느 범위에 속하느냐에 따라 작동횟수가 달라진다. 예를들어, 거리가 12보다 크고 17보다 작으면 작동횟수는 7회이다. 추가적으로, 각 범위의 개수가 규칙성을 띈다.

 

▷ 작동횟수 3과 4 : 2 개

▷ 작동횟수 5와 6 : 3 개

▷ 작동횟수 7과 8 : 4 개

 

이렇게 작동횟수가 2씩 증가 할 때마다,  범위 안에 포함된 개수는 1씩 증가한다. 그러므로 범위의 개수를 기준으로 값을 구해보자. 특정 거리가 어느 범위에 포함되는지 알려면 부등식을 써야한다.

 

▷ 작동횟수 2의 최댓값 : 2 ( 1개 )

▷ 작동횟수 3과 4의 최댓값 : 6 ( 2개 )

▷ 작동횟수 5와 6의 최댓값 : 12 ( 3개 )

▷ 작동횟수 7과 8의 최댓값 : 20 ( 4개 )

 

▶ 범위의 개수 : n

▶ 범위의 최댓값 : n*(n+1)

 

반복문을 통해, n을 1씩 증가시켜 입력된 거리가 어느 범위에 속하는지 파악하면 될 것 같지만 안 된다. 조건으로 제시된 정수의 범위가 굉장히 크다. (0 ≤ x < y < 2³¹)  하나씩 대입하여 반복문을 돌리면 시간초과가 된다. 

 

▷ 거리 : distance

임의의 수를 n이라고 하자.

distance <= n*(n+1) 이 성립되는 n을 구하려 한다. 

 

부등식은 반복문을 통해서 구현되지만 반복문은 시간초과가 난다. 그러므로 연산을 통해 구해야한다. 연산을 통해 구하려면 부등식을 조금 수정하면 된다.

 

▷ distance <= n*(n+1) < n² < (n+1)*(n+2)

▶ distance < n²

 

n의 제곱근은 Math.sqrt() 메소드로 구할 수 있다. 

 

▷ n = 4

▷ 13, 14, 15, 16, 17, 18, 19 ,20

 

Math.sqrt()로 계산하면 16(n²)보다 작은 수는 3.xx 큰 수는 4.xx이다.

그러나 3.xx는 3.5 이상이다. 고로, 반올림하면 4가 된다. 그러므로 Math.round() 메소드와 Math.sqrt() 메소드를 같이 이용하면 13, 14, 15, 16, 17, 18, 19 ,20 수들은 모두 4가 나온다. 

 

▶ n² 보다 크면 작동 횟수 : 2*n

▶ n² 과 같거나 작으면 작동 횟수 : 2*n - 1

 

 

3. 코드

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stz;
		
		int testcase = Integer.parseInt(br.readLine());
		
		for(int i=0; i<testcase; i++) {
			stz = new StringTokenizer(br.readLine());
			
			double x = Double.parseDouble(stz.nextToken());
			double y = Double.parseDouble(stz.nextToken());
			
			double distance = y - x;
			double n = Math.round(Math.sqrt(distance));
			
			if( distance <= Math.pow(n, 2)) {
				bw.write((int)(2*n-1)+"\n");
			}else {
				bw.write((int)(2*n)+"\n");
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}