[백준] 1011번 : Fly me to the Alpha Centauri - JAVA [자바]

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

1011번: Fly me to the Alpha Centauri

---

• 문제

 

생각보다 정답률이 낮은 문제다.

 

그러나 막상 규칙을 찾으면 매우매우 쉬운 문제이니 한 번 같이 풀어보자.

---

• 2가지 입력방법을 이용하여 풀이한다.

 

 

Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

 

---

• 알고리즘

필자가 항상 강조하지만 이러한 문제는 표나 그림을 그리라고 한다.

대부분의 경우 규칙이 있기때문에 조금만 나열해보면 금방 답이 나온다.

 

 

오히려 암산으로 하려 하면 코드를 짜는데 시간이 더 걸릴 수도 있다.

 

그럼 한번 같이 풀어보자.

 

 

먼저 우리는 X 와 Y 의 차이(거리)를 갖고 해당 거리에서 최소 이동 횟수를 찾아내야 한다.

그리고 이동하면서 한 번 이동할 때의 이동 거리 최댓값도 필요할 것 같으니 이 것도 변수를 둬보자.

 

거리 : Distance = Y - X

이동횟수 : Count

최댓값 : max

 

 

 

 

흠.. 이렇게 보니까 잘 감이 안온다. ( 이 표만 보고도 규칙을 찾아냈다면 대단하신거다. )

 

 

 

그러면 Count 를 기준으로 최대 거리를 한 번 표로 만들어보자.

그럼 아래와 같을 것이다.

 

 

 

Count 값에 따라 이동할 수 있는 최대 거리를 나열해보니 규칙이 세 가지 보인다.

1. max 가 1 씩 증가하면서 2 번씩 반복된다.
2. Distance(거리) 는 이전 거리와 최댓값과의 차이가 max 가 증가하는 규칙과 동일하다.
3. max 가 변하는 지점의 Distance 는 max 의 제곱 값이다.

 

 

무슨말인가 하면, Y - X, 즉 Distance 가 주어졌을 때, Distance 를 포함하는 범위를 쉽게 구할 수 있다는 의미다.

좀 더 구체적으로 표를 보면 한 번에 이해가 될 것이다.

 

 (move 필요 없을 것 같으니 표에서 제외시키겠다.)

 

노란색칸은 Count 가 변하는 지점,

녹색은 max 가 변하는 지점이다.

 

규칙이 보이는가? 아래 설명을 보자.

<규칙 1>

max 의 값은 distance 의 루트 값에서 소수점을 버린 정수값이랑 같다.

max = (int) Math.sqrt ( distance ) ;

 

(참고로 자바에서 루트 값을 구하는 메소드는 Math.sqrt() 이고 double 형이 return 된다.)

<규칙 2>

max 가 변하는 지점과 다음 지점 사이에는 항상 count 가 두 번씩 변한다.

즉, 녹색 구간 사이에 노란색 칸이 두 번 포함된다.

<규칙 3>

녹색 칸 다음에는 반드시 count (노란색) 가 변한다.

이는 당연한게 녹색칸은 Count 가 갈 수 있는 최대 거리이기 때문이다.

<규칙 4>

max 값이 변할 때의 Count 는 다음 수식을 따른다.

Count = ( 2 × max - 1 )

 

 

 

 

그럼 위를 토대로 조건문을 만들어보자.

 

먼저 X, Y 의 거리를 위 설명처럼 distance 로 두고, max 값 또한 규칙 1 에 따라 구해준다.

 

int distance = Y - X;
int max = (int)Math.sqrt(distance);	// 소수점 버림

 

 

다음으로 조건문을 차례대로 작성할 차례다.

 

가장 쉬운 것 부터 해보자.

 

 

 

< 첫 번째 조건문 >

max 는 distance 의 제곱근중 정수부분만 취한 값이다.

만약 정수부분만 취한 값과, 소수점까지 취한 값이 같다면?

9 는 제곱근이 3이고, 소수점을 버린 max 도 3 이다.

 

즉, 위와같이 distance 의 제곱근이 정수로 딱 떨어진다면 규칙 4에 의해 Count = ( 2 × max - 1 ) 가 된다.

 

int distance = Y - X;
int max = (int)Math.sqrt(distance);	// 소수점 버림

if(max == Math.sqrt(distance)) {
	print(2 * max - 1);
}

 

 

 

 

< 두 번째 조건문 >

 

max 의 제곱근이 정수로 떨어지는 경우는 제외되었으니 다음 구간부터 다음 max 이전 구간을 구해야 한다.

 

구간 중 일부분만 떼어서 생각해보자.

 

 

 

여기서 이미 9 하고 16 은 앞선 조건문에서 걸러졌다.

문제는 count 가 변하는 값이 두 번 있다는 것인데, 특징이 하나 있다.

 

다음과 같이 묶으면 묶인 개수는 max 값과 같다는 것을 알 수 있다.

이 구간만 그런 것이 아니라 다른 구간도 마찬가지다. ( 가장 긴 표 참고 )

 

 

그럼 첫 번째로 묶인 구간은 다음과 같을 것이다.

( max × max )   <   distance   ≤   ( max × max ) + max

 

그리고 해당 구간의 count 값은 다음과 같다.

count = 2 × max 

 

조건문을 추가하면 다음과 같을 것이다.

 

int distance = Y - X;
int max = (int)Math.sqrt(distance);	// 소수점 버림

if(max == Math.sqrt(distance)) {
	print(2 * max - 1);
}
else if(distance <= max * max + max) {
	print(2 * max);
}

 

( 선행 조건문에서 이미 max × max 부분은 걸러졌으니 최소 조건은 필요가 없다. )

 

 

 

 

 

< 세 번째 조건문 >

 

두 번째 구간의 조건은 else 문으로 해결하면 끝나므로 count 가 몇이 되는지만 알면 된다.

해당 구간의 count 는 다음과 같다.

 

count = 2 × max + 1

 

그럼 코드로 짜면 다음과 같을 것이다.

 

int distance = Y - X;
int max = (int)Math.sqrt(distance);	// 소수점 버림

if(max == Math.sqrt(distance)) {
	print(2 * max - 1);
}
else if(distance <= max * max + max) {
	print(2 * max);
}
else {
	print(2 * max + 1);
}

 

 

이게 끝이다!

생각보다 쉽게 풀리지 않는가?

 

굳이 반복문이나 재귀로 돌려서 count 값이 일치할 때까지 찾을 필요 없이 수식만으로 해결 할 수 있다.

 

그럼 완성된 코드를 보자.

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);

		int T = in.nextInt();	// 테스트 케이스 
		
		for(int i = 0; i < T; i++) {
        
			int X = in.nextInt();
			int Y = in.nextInt();
			
			int distance = Y - X;	// 거리
			
			int max = (int)Math.sqrt(distance);	// 소수점 버림
            
			if(max == Math.sqrt(distance)) {
				System.out.println(max * 2 - 1);
			}
			else if(distance <= max * max + max) {
				System.out.println(max * 2);
			}
			else {
				System.out.println(max * 2 + 1);
			}
			
		}
	}
}

 

 

가장 기본적인 방법이다.

---

- 방법 2 

 

 

BufferedReader 을 쓰는 방식이다.

 

그리고 반드시 자료형 타입을 잘 보아야 한다.

br.readLine() 은 문자열로 데이터를 읽으니 반드시 꺼내서 쓸 때 int 형으로 쓰고자 한다면 Integer.parseInt()로 String 을 int 형으로 변환시켜준다.

 

또한 문자열 분리를 위해 StringTokenizer 을 사용할 것이고,

테스트 케이스만큼 반복 출력을 하는 것보다는 StringBuilder 을 통해 하나로 묶어 한 번에 출력하고자 한다.

 

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));
		StringBuilder sb = new StringBuilder();
		
		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 max = (int)Math.sqrt(distance);
			
			if(max == Math.sqrt(distance)) {
				sb.append(max * 2 - 1).append('\n');
			}
			else if(distance <= max * max + max) {
				sb.append(max * 2).append('\n');
			}
			else {
				sb.append(max * 2 + 1).append('\n');
			}
			
		}
		System.out.println(sb);
	}

}

 

 

 

 

 

 

---

• 성능 차이

위에서 부터 순서대로

 

채점 번호 : 18985007  -  BufferedReader

채점 번호 : 18984882  -  Scanner

 

 

확실히 성능은 BufferedReader 가 좋다.

 

그리고 아마 반복문으로 짰다면 위 시간보다 더 긴 시간이 소요되었을 것이다.

---

• 정리

수학문제의 경우 대부분 보면 아주 단순한 문제다.

대부분 규칙이나 연산식을 일관성 있게 정리할 수 있게 되어 있다.

 

다만, '정리'를 해야 쉽다.

 

특히 이번 문제같은 경우 필자가 풀고나서 java 로 푼 사람들의 코드를 보니 반복문으로 푼 사람들이 꽤 많았다.

그리고 암산처럼 풀다보니 정답률이 낮았던 것 같다.

 

물론 그렇게 풀어도 된다만, 수학 문제인만큼 수학적으로 접근하는 것이 본 취지에도 맞고, 코드를 작성하는 시간 또한 절약할 수 있다.

 

앞으로도 많은 문제들이 나올텐데 필자가 알려준 코드를 그대로 복붙해서 제출하기 전에 한 번 직접 풀어보는 것을 추천드린다.