[백준 1011] Fly me to the Alpha Centauri [C]

백준 - 1011

---

풀이

입력받은 지점사이의 거리(y-x)는 다음과 같은 규칙성이 존재한다.

• 거리의 제곱근의 정수를 기준으로 구간이 나뉜다. (ex : 3.0 ~ 3.xx, 4.0 ~ 4.xx), 제곱근의 정수를 n이라고 한다.
• 거리가 n*n 일때 작동 횟수는 2n - 1번이다. (빨간색)
• 거리가 n*n보다 크고, n*n + n 이하일 때 작동 횟수는 2n번이다. (초록색)
• 거리가 n*n + n보다 크고, (n+1)*(n+1)미만 일 때 작동 횟수는 2n + 1번이다. (파랑색)

거리	작동 횟수	이동 기록
1	1	1
2	2	11
3	3	111
4	3	121
5	4	1211
6	4	1221
7	5	12211
8	5	12221
9	5	12321
10	6	123211
11	6	123221
12	6	123321
13	7	1233211

---

소스코드

#include <stdio.h>
#include <math.h>
int main(){
    int T, x, y, n, distance;
    scanf("%d", &T);
    while (T--){
        scanf("%d %d", &x, &y);
        n = sqrt(distance = y-x);
        if (distance == n*n)
            printf("%d\n", 2*n-1);
        else
            printf("%d\n", distance <= n*n + n ? 2*n : 2*n+1);
    }
}

---

출처

1011번: Fly me to the Alpha Centauri