[C언어 백준 풀이][Gold V] 1011번 : Fly me to the Alpha Centauri (제곱근 sqrt 활용 조건식)

이 포스트에는 백준 Online Judge의 1101번 문제인 Fly me to the Alpha Centauri에 대한 풀이 코드와 해설이 정리되어 있습니다. (Solved.ac 기준 난이도 Gold V)

 

 

1011번 : Fly me to the Alpha Centauri

 

이전 이동에서 k의 거리를 이동했을 때, 다음 이동에서 k-1, k, k+1 중 하나의 거리만큼 이동이 가능하고 처음 이동과 마지막 이동은 1만큼 이동한다고 할 때 x에서 y까지 이동하기 위한 최소 이동 횟수를 구하는 문제입니다.

 

 

규칙성을 찾기 위해 합을 위와 같이 적어보면, 거리(수의 갯수)가 변화하는 직전의 수에서 규칙을 발견할 수 있습니다.

이 수들은 모두 1+2+ ... +N-1+N+N-1+ ... +2+1 또는 1+2+ ... +N-1+N+N+N-1+ ... +2+1 꼴이므로 이를 이용하여 각 거리에 해당하는 경계선을 알아낼 수 있습니다.

 

#include<stdio.h>

int main() {
    int T, x, y, temp, sum, count;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        scanf("%d %d", &x, &y);
        if(x > y) {
            temp = x;
            x = y;
            y = temp;
        }
        sum = count = 0;
        for(int i=1; ; i++) {
            sum += i, count++;
            if(sum >= y-x) break;
            sum += i, count++;
            if(sum >= y-x) break;
        }
        printf("%d\n", count);
    }
}

 

그래서 초기에는 코드를 위와 같이 (접은글 내부에 적어둠) 작성하였으나, 시간 초과가 발생하여 반복문으로 값을 찾기보다는 정형화 된 계산식을 이용하는 방식으로 풀어야 했습니다.

 

#include<stdio.h>
#include<math.h>

int main() {
    int T, x, y, temp, root;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        scanf("%d %d", &x, &y);
        if(x > y) {
            temp = x;
            x = y;
            y = temp;
        }
        root = sqrt(y-x);
        if(y-x == root*root) printf("%d\n", 2*root-1);
        else if(y-x > root*(root+1)) printf("%d\n", 2*root+1);
        else printf("%d\n", 2*root);
    }
}

 

최종적으로는 제곱근을 이용하여 구간을 바로 구하는 방식을 이용했습니다.

( i ) y-x(거리)가 제곱수인 경우, root*root = y-x이고 이 경우는 규칙성에 따라 2*root-1을 출력해주어야 합니다.

  구간을 이용하지 않고 y-x == root*root의 조건식을 이용한 이유는, y-x가 1만 작아져도 root 값이 정수형이기 때문에 root 값 역시 변화하기 때문입니다. (y-x = 15가 되면 root가 3으로 바뀜)

이제 나머지 경우는 모두 root*root 값이 y-x보다 작아지므로, root*root < y-x의 조건식은 굳이 필요하지 않습니다.

( ii ) y-x > root*(root+1)의 조건식에서 분기가 나뉘어지는데, 이는 거리에 따른 이동 횟수를 표로 나타내어보고 규칙성을 찾을 수 있습니다.

root 값이 1 감소된 상태이므로 이를 고려하여 식을 작성해주어야 합니다.

( iii ) 그 외 나머지 경우는 y-x <= root*(root+1)의 경우이므로 ( ii ) 케이스보다 1 더 작은 이동 횟수를 출력해야 합니다.

 

결국 시간 초과를 발생시키지 않기 위해 거리에 대한 함수로써 이동 횟수를 식으로 유도하는 문제였는데, 이 식을 유도하는 과정이 까다로웠던 문제였습니다.

반복문을 이용하지 않고 제곱근을 이용하여 구간을 바로 찾아내는 방식 자체가 좋은 아이디어인 문제인 것 같습니다.