백준 1011_Fly me to the Alpha Centauri

 

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

1 2 2 3 3 4 4 5 5 6 6 으로 더해지면서 이동 횟수가 늘어나는 규칙으로

아래와 같이 짰는데, 시간초과가 나왔었다.

#include <stdio.h>
long func(long r)
{
        int i,j;
        int cnt;
        if(r<=2)
                return r;

        int sum=2;
        int n=2;
        cnt=2;
        while(1){
                for(i=0; i<2; i++){
                        sum += n;
                        cnt++;
                        if(sum>=r) return cnt;
                }
                n++;
        }
}

void print(const long *arr, int t)
{
        int i;
        for(i=0; i<t; i++)
                printf("%ld\n", arr[i]);
}

int main()
{
        int T;
        long x,y;
        int i;
        scanf("%d", &T);
        long result[T];
        for(i=0; i<T; i++){
                scanf("%ld %ld", &x, &y);
                result[i] = func(y-x);
        }

        print(result, T);

        return 0;

}

 

 

자세히 보면

횟수	1	2	3	3	4	4	5	5	5	6	6
y-x	1	2	3	4	5	6	7	8	9	10	11
이동	1	11	111	121	1211	1221	12211	12221	12321	123211	123221

 

거리가 1, 4, 9, 16 ... 으로 제곱수가 될 때마다 12...n...21의 형태를 가진다.

제곱수 기준으로 대칭을 이룬다.

3 3(제곱수:4) 4 4

5 5 5(제곱수:9) 6 6 6 

 

최소 워프 횟수는...

y-x가 n^2일 때, 작거나 같은 영역에 있으면, 횟수는 n*2-1

y-x가 n^2일 때, 보다 큰 영역에 있으면, 횟수는 n*2

 

 

.

.

.

.

.

아래와 같이 바꾸면

#include <stdio.h>
long long func(long long r)
{
        long long i, cnt;
        long long pow, pow1, pow2;
        for(i=1; ; i++){
                pow = i*i;
                pow1 = pow - i + 1;
                pow2 = pow + i;
                if(pow1 <= r && pow2 >= r){
                        if(r <= pow)
                                cnt = i*2 -1;
                        else
                                cnt = i*2;
                        return cnt;
                }
        }
}

void print(const long long *arr, long long t)
{
        long long i;
        for(i=0; i<t; i++)
                printf("%lld\n", arr[i]);
}

int main()
{
        long long T;
        long long x,y;
        long long i;
        scanf("%lld", &T);
        long long result[T];
        for(i=0; i<T; i++){
                scanf("%lld %lld", &x, &y);
                result[i] = func(y-x);
        }

        print(result, T);

        return 0;
}

type은 long long으로 해줬다.