[BAEKJOON] 1011번

#include <stdio.h>
 
#define SQUARE(X) ((X)*(X))
 
int run();
long long warp(long long d);
 
int main()
{
    return run();
}
 
int run()
{
    int num;
    long long x, y;
 
    scanf("%d", &num);
 
    while (--num)
    {
        scanf("%lld %lld", &x, &y);
 
        printf("%lld\n", warp(y - x));
    }
 
    return 0;
}
 
long long warp(long long d)
{
    long long j;
    long long min, sqr, max;
    for (j = 1; ; ++j)
    {
        sqr = SQUARE(j);
        min = sqr - (j - 1);
        max = sqr + j;
        
        if ((min <= d) && (d <= sqr))
        {
            return ((j << 1) - 1);
        }
        else if ((sqr < d) && (d <= max))
        {
            return (j << 1);
        }    
    }
}
 

거리마다 공간 이동 장치 작동 횟수는 다음과 같다.

거리	이동 단계(거리)	공간 이동 장치 작동 횟수
1	1	1
2	1 - 1	2
3	1 - 1 - 1	3
4	1 - 2 - 1	3
5	1 - 2 - 1 - 1	4
6	1 - 2 - 2 - 1	4
7	1 - 2 - 1 - 2 - 1	5
8	1 - 2 - 2 - 2 - 1	5
9	1 - 2 - 3 - 2 - 1	5
10	1 - 2 - 2 - 2 - 2 - 1	6
11	1 - 2 - 3 - 2 - 2 - 1	6
12	1 - 2 - 3 - 3 - 2 - 1	6
13	1 - 2 - 3 - 3 - 2 - 1 - 1	7
14	1 - 2 - 3 - 3 - 2 - 2 - 1	7
15	1 - 2 - 3 - 3 - 3 - 2 - 1	7
16	1 - 2 - 3 - 4 - 3 - 2 - 1	7
17	1 - 2 - 3 - 4 - 3 - 2 - 1 - 1	8
18	1 - 2 - 3 - 4 - 3 - 2 - 2 - 1	8
19	1 - 2 - 3 - 4 - 3 - 3 - 2 - 1	8
20	1 - 2 - 3 - 4 - 4 - 3 - 2 - 1	8
21	1 - 2 - 3 - 4 - 4 - 3 - 2 - 1 - 1	9
22	1 - 2 - 3 - 4 - 4 - 3 - 2 - 2 - 1	9
23	1 - 2 - 3 - 4 - 4 - 3 - 3 - 2 - 1	9
24	1 - 2 - 3 - 4 - 4 - 4 - 3 - 2 - 1	9
25	1 - 2 - 3 - 4 - 5 - 4 - 3 - 2 - 1	9
26	1 - 2 - 3 - 4 - 5 - 4 - 3 - 2 - 1 - 1	10
27	1 - 2 - 3 - 4 - 5 - 4 - 3 - 2 - 2 - 1	10
28	1 - 2 - 3 - 4 - 5 - 4 - 3 - 3 - 2 - 1	10
29	1 - 2 - 3 - 4 - 5 - 4 - 4 - 3 - 2 - 1	10
30	1 - 2 - 3 - 4 - 5 - 5 - 4 - 3 - 2 - 1	10
31	1 - 2 - 3 - 4 - 5 - 5 - 4 - 3 - 2 - 1 - 1	11

규칙은 다음과 같다.

① 거리는 제곱수 (n², n=1, 2, 3, …) 를 기준으로 양쪽으로 일정 범위에 속하게 된다.

② 거리가  [n² - (n - 1), n²] 일 경우 공간 이동 장치 작동 횟수는  2n - 1 이고,

    거리가  [n², n²+n] 일 경우 공간 이동 장치 작동 횟수는  2n 이다. 

이를 그대로 코드에 옮기면 된다.

 j 를  1 부터 시작해  1 씩 늘리며, 주어진 거리가 각 구간에 속하는지 검사한다.

그런데 왜  long long 을  int 로 바꾸면 시간 초과가 발생하는 걸까..

: 2019/04/08

32bit OS에서는 int형(4byte)이 제일 빠르니까 64bit에서는 long long형(8byte)이 제일 빠른 게 아닐까 싶다.