day6 백준 1011번 : Fly me to the Alpha Centauri [Java]

문제 출처

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

1011번: Fly me to the Alpha Centauri

import java.util.Scanner;
public class day006_Q1011 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for(int i =0 ; i < T; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			int position = x;
			int count = 0;
			int k = 1;
			
			position++;
			count++;
			
			if(position == y) {System.out.println(count); break;}
			
			while(position != y - 1) {
				if(position + (k + 1) <= y - 1) {
					position += (k + 1);
					k = k + 1;
					count++;
					continue;
				}
				else if(position + k <= y - 1) {
					position += k;
					count++;
					continue;
				}
				else {
					position += (k - 1);
					k = k - 1;
					count++;
					continue;
				}
			}
			
			position++;
			count++;
			
			System.out.println(count);
		}
		
		sc.close();
	}

}

정말 어쩜 한번에 맞는 일이 이렇게 없을까?

위 코드는 시간초과가 나왔다. 

0 2147483647을 입력하니 이클립스상에서도 시간이 상당히 오래걸렸고 답이라고 나온 숫자도 딱봐도 답이 아닌 이상한 숫자가 나왔다.

 

질문게시판에 시간초과 관련 글들을 찾아봤는데 int를 long으로 바꿔보라는 답변이 많아서 그대로 해봤으나 여전히 안됐다.

내 코드 자체의 문제라는것...

 

우선 처음에는 반드시 한칸밖에 이동을 못하니 한칸을 전진 시켜놓고 생각했다.

마지막에는 반드시 한칸만 이동해야하므로 사실상 y-1까지 최소 거리로 도달한다음 마지막으로 count를 플러스 해주면 될거라고 생각했다.

하지만 한가지 생각 못한거는 마지막에 한칸을 이동하려면 y-1에 도달하기 직전에 최대 2칸 움직여야한다.

 

사실 이문제 이틀을 고민했는데 못 풀어서 구글링의 힘을 받았다...ㅠㅠ

이 문제를 풀고 얻은 교훈은 이런 문제를 풀때 규칙을 찾을것!

 

import java.util.Scanner;
public class day006_Q1011 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for(int i =0 ; i < T; i++) {
			long x = sc.nextLong();
			long y = sc.nextLong();
			
			long distance = y - x;
			int count;
			int max = (int)Math.sqrt(distance);
			
			if(max == Math.sqrt(distance)) {
				count = 2 * max - 1;
			}
			else if(max * max + max >= distance) {
				count = 2 * max;
			}
			else {
				count = 2 * max + 1;
			}
			
			System.out.println(count);
		}
		
		sc.close();
	}

}