[BaekJoon] 백준 1011번 _Fly me to the Alpha Centauri for JAVA

 

 

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

1011번: Fly me to the Alpha Centauri

 

 

 

 

 

 

 

 

---

 

 

 

먼저 문제를 보고 2^31값까지 가능하므로 int값을 사용하기로 하였다.

 

 

이 문제에서 중요한 것을 x와 y의 값보다는 x와 y의 거리이다. 그래서 y - x 값인 거리값을 사용할 것이다.

 

 

 

 

문제가 너무 복잡하니까 표로 정리해서 어떤 값을 넣으면 어떤 값이 나오는지 확인해보자!!

 

 

 

거리	move	count (출력값)	max움직임
1	1	1	1
2	1 1	2	1
3	1 1 1	3	1
4	1 2 1	3	2
5	1 2 1 1	4	2
6	1 2 2 1	4	2
7	1 1 2 2 1	5	2
8	1 2 2 2 1	5	2
9	1 2 3 2 1	5	3
10~12		6	3
13~15		7	3
16		7	4

 

 

 

이런식으로 진행된다.

 

 

눈여겨봐야할 지점은 max 움직임이다!

 

max 움직임 1일 때 거리: 1~3, 2일 때 거리: 2~8, 3일 때 거리: 9~15 이런식으로 흘러가므로

거리의 루트값과 관련이 있음을 알 수 있다.

 

 

 

 

여기서 max 움직임이 2일 때 값을 살펴보자!

 

 

 

 

 

이렇게 진행된다. max움직임이 2값이 아닌 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 Baek1011 { // Fly me to the Alpha Centauri
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			int distance = y - x;
			int count = 0;
			
			int max = (int)Math.sqrt(distance); // 소숫점 버리기
			
			if(max * max == 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();
		br.close();
		
	}
}

 

 

다음과 같이 코드를 짤 수 있다.

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

사실 이 문제는 정해놓은 시간 안에 풀지 못해서 다른 사람의 코드를 이해하고 참고하였다.ㅠㅠ

 

 

이런 수학 문제를 풀 때는 패턴을 찾기 위해 표를 이용하면 좋다는 것을 깨달았고

 

 

나는 BufferedWriter를 사용하였는데 StringBuffer나 StringBuilder를 사용하는 것이 성능이 더 좋았다.

 

 

 

다음에는 StringBuffer를 사용해야겠다!!