백준 1011번 C언어 풀이

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

최소 이동 횟수를 구하는 문제. 어쩔 수 없이 직접 이동 거리를 써보면서 규칙을 찾아야 한다.

 

맨 마지막 이동거리는 1이어야만 하고 맨 처음 출발 역시 1로 시작해야 한다.

 

거리가 26일때 까지만 써보자

거리 (y-x)	이동	횟수
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 2 1 1	5
8	1 2 2 2 1	5
9	1 2 3 2 1	5
10	1 2 3 2 1 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

규칙찾기가 참 힘들다. 하지만 써보다보면 어느정도의 규칙이 보이기 시작한다. 거리d가 제곱수인 경우 sqrt(d)에 대칭적임을 알 수 있다 (4 : 1 2 1 이므로 2에 대칭) 그러므로 제곱수인 경우는 2sqrt(d)-1번 이동해야 한다.

 

문제는 이 다음이다. 제곱수가 아닌 경우에는 어떻게 해야하는가? 거리가 4~9일때를 예로 들어보자. 6의 경우 9보다는 4와 가깝기 때문에 4일때의 이동 횟수+1값을 갖는다, 7의 경우 4보다 9에 가깝기 때문에 9의 이동횟수값을 갖는다.

 

처음에는 두 제곱수간의 거리로 이동거리를 계산해야하나 샆었지만, 한가지 증명아닌 증명을 통해 계산을 편하게 할 수 있었다.

 

인접한 제곱수 a, b가 있다고 하자 (a < b, ex. a=4, b=9). a와 b는 동시에 홀수나 짝수가 될 수 없다. 따라서 a, b의 중앙값은 ~.5가 나오게 된다. 따라서 중앙값에 가장 인접한 두 자연수는 중앙값의 ±0.5의 값을 갖는다. 이 두 수의 제곱근 값을 살펴보자. a와 b는 같은 n값에 대해 각각 n^2, (n+1)^2로 나타낼 수 있다. 이제 다음을 증명하면 된다.

a보다 크고 중앙값보다 작은 자연수의 제곱근 값은 a의 제곱근, 즉 n값에 0.5를 더한값보다 작고, 중앙값보다 크고 b보다 작은 자연수의 제곱근 값은 n에 0.5를 더한 값보다 크다는 것이다. 이를 증명하면 단지 거리의 제곱근값의 2배를 한 후에 소수점을 버리면 답이 된다. (이 식이 참이라는걸 전제로 하고 살펴보자면) 6의 제곱근값은 대략 2.45로 2.5를 넘지 않는다. 하지만 7의 경우 대략 2.65로 2.5를 넘는다. 각각 2배를 하고 소수점을 버리면 6의 경우 4가 되고 7은 5가 된다. 그리고 이 두 수는 6과 7일때의 이동횟수랑 정확히 들어맞는다.

 

부등식의 각 항을 좀만 정리하면 자명해지므로 정리해보면

이다. 이제 코드에 적용해보자.

 

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

int main () {
    int t;
    int x, y;
    double dis;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &x, &y);
        dis = sqrt(y-x);
        if (dis == (int)dis) { // 거리가 제곱수라면 2sqrt(n)-1회
            printf("%d\n", 2 * (int)dis - 1);
        } else {
            printf("%d\n", (int)(2 * dis));
        }
    }
}

 

두번째로 풀어보는 골드문제이다. 진짜 어렵다