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 |