smooth waters run deep

1d-1c/BOJ

1011_Fly me to the Alpha Centauri (JAVA)

yeon_11 2020. 10. 20. 16:17
 

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행

www.acmicpc.net

 

import java.util.Scanner;

public class Main {
	static int start;
	static int end;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int i=0; i<T; i++){
			start = sc.nextInt();
			end = sc.nextInt();

			int ans = move(start, end);
			System.out.println(ans);
		}
	}

	public static int move(int x, int y){
		int term = y-x; //start-end 사이간 거리
		int ans = 0;
		if(term == 2) ans = 2;
		else if(term == 3) ans = 3;
		else{
			int i = (int)Math.sqrt(term);
			if(Math.sqrt(term) == i) //제곱수일때
				ans = (int)Math.sqrt(term)*2 - 1;
			else if(i*i<term && term<=i*i+i) //i^2 ~ 중간값 사이에 해당할때
				ans = 2*i;
			else ans = 2*i+1; //중간값 ~ (i+1)^2 사이에 해당할때
		}
		return ans;
	}
}

 

[출력 예시 해석]

 

1) 시작 0 ~ 도착3

     111 : 출력 3, 시작-도착 사이 거리=3

2) 시작1 ~ 도착5

     121 : 출력 3, 시작-도착 사이 거리=4

3) 시작45 ~ 도착50

     1211 : 출력 4, 시작-도착 사이 거리=5

 

 

출력이 어떻게 되는지는 이해했는데, 어떤 규칙이 있는지는 도저히 모르겠어서 하나씩 다 세어봄..!

 

시작 ~ 도착 사이의 거리를 기준으로 나타내어보면 다음과 같다.

제곱수를 기준으로 규칙을 파악할 수 있다.

 

1) 제곱수일 경우

     1^2, 2^2, 3^2, ... , i^2 와같은 제곱수라면 - 출력결과는 2*i-1 이 된다.

     제곱수를 판단하기 위해 Math.sqrt()를 이용했다.

     double을 리턴하므로, Math.sqrt()값과 (int)Math.sqrt()값이 같다면 제곱수로 판단!

 

2) 제곱수 ~ 다음 제곱수 사이에 위치할 경우

     예를 들면, 4~9 사이에서의 변화를 보자. 출력결과가 4, 7, 9에서 변화되는 걸 볼 수 있다.

     7 = 4 + (9-4-1)/2 의 값으로, i를 이용해 일반화해보면 - i^2 + ((i+1)^2-i^2-1)/2 = i^2+i 로 나타낼 수 있다.

 

     ① i^2 ~ (i^2, (i+1)^2 사이의 중간값) 에 위치한다면

          예를 들면, 5,6 일때 == 4~7 사이의 수일때          

          출력결과 : 2*i

     ② (i^2, (i+1)^2 사이의 중간값) ~ (i+1)^2 에 위치한다면

          예를 들면, 7,8 일때 == 7을 포함한 7~9 사이의 수 일때

          출력결과 : 2*i+1

 

 

 

'1d-1c > BOJ' 카테고리의 다른 글

2581_소수 (JAVA)  (0) 2020.10.20
1978_소수 찾기 (JAVA)  (0) 2020.10.20
2775_부녀회장이 될테야 (JAVA)  (0) 2020.10.18
10250_ACM 호텔 (JAVA)  (0) 2020.10.18
2869_달팽이는 올라가고 싶다 (JAVA)  (0) 2020.10.18