[[problem:ARCTIC]]

안녕하세요 한창 배워가는 개발자입니다.
위 문제는 '정답' 을 받기는 했지만, 성능상 이해가 되지 않는 부분이 있어 이렇게 문의를 드리게 되었습니다.
고수님들의 고견 부탁드립니다.

<궁금한점>
메모이제이션으로 최대 97% 정도 sqrt() 연산을 줄였음에도 수행시간은 미묘하게 더 걸리는 것 같습니다. 어떤 이유 때문일까요? (참고로, 제가 LOCAL 에서 테스트 했을때는 2배 가량 수행속도가 빨랐습니다.)

<비교가 필요한 함수>
- getDistance1() : 그냥 코드
- getDistance() : 메모이제이션 고려한 코드

~~~ c++
/*
1) A = {본부}
2) A 집합의 각 원소와 가장 근접한 기지 탐색
3) 탐색된 기지를 A에 추가
4) 추가할때 A 집합에 속한 기지와 탐색된 기지의 거리를 구하여, 최대가 되는 값이 정답임
5) 2,3 반복
6) memoization 으로 거리 계산 중복 연산 제거
*/
#include
#include
#include
unsigned long called;

int TC;
int posN;
float pos[100][3];
int setN;
float set[100][2];
float setmemo[100][100];
float answer;
float dist;
float jmin, kmin;
int jidx, kidx;

int insertSet(int idx)
{
set[setN][0] = pos[idx][0];
set[setN][1] = pos[idx][1];
pos[idx][2] = 1;
return ++setN;
}

float getDistance1(float x1, float y1, float x2, float y2)
{
called++;

return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

}
float getDistance(int j, int k)
{
if(setmemo[j][k] != 0) {
return setmemo[j][k];
}
else {
called++;

    setmemo[j][k] = sqrt((set[j][0] - pos[k][0])*(set[j][0] - pos[k][0]) + (set[j][1] - pos[k][1])*(set[j][1] - pos[k][1]));        
}
return setmemo[j][k];

}
int main(void)
{
clock_t start= clock();
freopen("input.txt", "r", stdin);
setbuf(stdout, NULL);

scanf("%d", &TC);
for(int i=0;i<TC;i++)
{
    // input
    scanf("%d", &posN);
    for(int j=0;j<posN;j++)
    {
        scanf("%f %f",&pos[j][0], &pos[j][1]);
        pos[j][2] = 0;
    }

    // init
    answer = 0;
    setN = 0;
    for(int j=0;j<posN;j++)
        for(int k=0;k<posN;k++)
            setmemo[j][k] = 0;

    // code
    insertSet(0);   // 본부를 집합에 포함시킨다.

    while(setN<posN)
    {
        jmin = 2000;
        kmin = 2000;
        for(int j=0;j<setN;j++)
        {
            for(int k=0;k<posN;k++)
            {
                if(pos[k][2] == 1) continue;    // 이미 set 에 포함되었으면 continue

                //dist = getDistance1(set[j][0], set[j][1], pos[k][0], pos[k][1]);
                dist = getDistance(j,k);    // memoization

                if(kmin > dist) {
                    kmin = dist;
                    kidx = k;
                }
            }

            if(jmin > kmin) {
                jmin = kmin;
                jidx = kidx;
            }
        }

        insertSet(jidx);    // 선택된 집합과 가장 거리가 가까운 기지를 포함시킨다.

        if(answer < jmin) answer = jmin;
    }

    // output
    printf("%.2f\n", answer);
}

printf("\ntime : %d %ld\n",clock()-start,called);

return 0;

}
~~~