[백준/C언어] 1011번 - Fly me to the Alpha Centauri

백준 웹사이트 "1011번 - Fly me to the Alpha Centauri" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1011번: Fly me to the Alpha Centauri

---

소스 코드

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

int main(void){
    int T;
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int x, y; // 조건에 의해 2^31보다 작으므로 'int'로 표현 가능
        scanf("%d %d", &x, &y);

        int distance = y-x; //distance>1
        int n = (int) sqrt((double) distance); // sqrt: input/output 모두 double

        // 이 시점에서, n^2 <= distance < (n+1)^2
        // 1. distance = n^2 이면 n+(n-1)회
        // 2. n^2 < distance <= n*(n+1) 이면 2n회
        // 3. n*(n+1) < distance < (n+1)^2 이면 (n+1)+n회
        int num;
        if(distance == n*n){
            num = n+(n-1);
        }
        else if(distance <= n*(n+1))
            num = 2*n;
        else
            num = (n+1)+n;
        printf("%d\n", num);
    }
}

---

문제 풀이

  문제를 어떻게 풀어야할지 감이 잘 오지 않을 때는, 거리가 1일 때부터 횟수들을 하나씩 구해보면서 규칙을 찾아보는 것이 좋습니다.

1    (1 = 1*1)
1 1    (2 = 1*2)
1 1 1
1 2 1    (4 = 2*2)
1 2 1 1
1 2 2 1    (6 = 2*3)
1 2 2 1 1
1 2 2 2 1
1 2 3 2 1    (9 = 3*3)
1 2 2 2 2 1
1 2 3 2 2 1
1 2 3 3 2 1    (12 = 3*4)
1 2 3 2 2 2 1
1 2 3 3 2 2 1
1 2 3 3 3 2 1
1 2 3 4 3 2 1    (16 = 4*4)

경우들을 나열하다보니, 어느 정도의 규칙이 보입니다. '홀수번 횟수'만큼 갈 경우, "1 2 3 2 1"이나 "1 2 3 4 3 2 1"과 같이 "1 2 .. \(n\) .. 2 1" 형태일 때 최대입니다. 이때 거리는 이들의 합인 \(n^2\)이므로, \(n+(n-1)\)번의 이동으로 갈 수 있는 최대 거리는 \(n^2\)인 셈입니다. 마찬가지로 '짝수번 횟수'만큼 갈 경우, "1 2 2 1" 이나 "1 2 3 3 2 1"과 같이 "1 2 .. \(n\) \(n\) .. 2 1" 형태일 때 최대입니다. 이때 거리는 이들의 합인 \(n(n+1)\)이므로, \(2n\)의 이동으로 갈 수 있는 최대 거리는 \(n(n+1)\)입니다. 이러한 규칙을 생각하고 코드를 작성해봅시다.

  규칙을 살펴보면, 1, 4, 9, ... 와 같은 제곱수들을 기준으로 횟수가 나뉩니다. 따라서 거리(변수 'distance')가 어떤 제곱수들 사이에 위치하는지 확인하는 것이 우선입니다. Line 13에서 'sqrt' 함수를 이용해 알아보는데, <math.h>에 포함되는 sqrt 함수의 input, output이 모두 double형이므로, 자료형 변환을 신경써줍니다. Line 13을 통해 \(n\)이 구해지면, distance의 범위는 \(n^2 \leq distance < (n+1)^2\)이 됩니다. 이때, 가능한 이동 횟수로 아래와 같이 3가지가 있습니다.

범위: \(n^2 \leq distance < (n+1)^2\)

1. \(distance = n^2\)인 경우: \(n+(n-1)\) 회 
2. \(n^2 < distance \leq n(n+1)\)인 경우: \(2n\) 회
3. \(n(n+1) < distance < (n+1)^2\)인 경우: \((n+1)+n\) 회

이렇게 3가지 경우를 고려하여 Line 20 ~ 26를 거치면 변수 'num'에 알맞은 이동 횟수가 저장됩니다. 저의 풀이와 다른 풀이도 분명 많을텐데, 각자 문제를 푸실 때 반복문은 꼭 빼주세요! 시간 제한이 2초로 비교적 길어서 첫 시도에서는 while문을 이용했는데, '시간 초과'가 떴습니다. 아마 테스트케이스 T가 꽤나 많은 예제도 존재하는 것 같습니다ㅎㅎ.