백준 1011번 Fly me to the Alpha Centauri(Java)

규칙을 찾기가 어려웠던 문제. 중간에 계산을 잘못해서 푼 줄 알았는데 알고보니 틀렸었다. 뭔가 규칙이 보일듯 말듯 한데 잘 보이지 않아서 고생했다.

 

조건

• 시작할때와 목적지에 도달 전의 이동거리는 반드시 1이 되어야 한다.
• 이동 가능한 거리는 바로 전에 이동했던 거리(n)의 n-1, n, n+1만큼 이동할 수 있다.

이런 문제를 풀때는 반드시 어딘가에 경우의 수를 써가면서 풀자. 암산하려고 하면 더 어렵고 헷갈린다.

 

 

거리(y-x)	경로	가장 큰 이동거리	작동횟수
1	1	1	1
2	11	1	2
3	111	1	3
4	121	2	3
5	1211	2	4
6	1221	2	4
7	12211	2	5
8	12221	2	5
9	12321	3	6

위 표를보면 몇가지 규칙이 있다. 

1. 거리가 제곱일때 그 가장 큰 이동거리가 1증가 한다.

2. 거리가 제곱일때 그 다음 거리의 작동횟수는 1증가한다.

 

아직 이정도 가지고 문제를 풀 수 없다. 규칙을 더 구해보자.

거리	1	2	3	4	5	6	7	8	9
가장 큰 이동거리	1	1	1	2	2	2	2	2	3
작동 횟수	1	2	3	3	4	4	5	5	5

10	11	12	13	14	15	16	17	18	19
3	3	3	3	3	3	4	4	4	4
6	6	6	7	7	7	7	8	8	8

규칙이 또 다른것이 보인다!  가장 큰 이동거리는 거리의 제곱근중 정수부분이고, 가장 큰 이동거리가 바뀔때 작동횟수는 (2*가장 큰 이동거리 -1)가 성립한다. 또한 작동 횟수가 같은것은 가장 큰 이동거리와 같은수다.

 

즉 이러한 조건을 정렬하면

1. 거리가 제곱일때 작동횟수는 (2* 가장 큰 이동거리-1)이다.

2.가장 큰 이동거리는 작동횟수의 개수와 같다. 즉 거리가 (가장 큰 이동거리 * 가장 큰 이동거리)+가장 큰 이동거리는 작동 횟수가 2*가장 큰 이동거리다.

3.그 외에는 작동횟수는 2*가장 큰 이동거리+1이다.

4. 

이를 코드로 표현하면 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        long count= scanner.nextLong();
        for(int i=0;i<count;i++) {
            long start = scanner.nextLong();
            long destination = scanner.nextLong();
            long distance = destination - start;
            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);
        }
    }
}