숨바꼭질6 _ 백준 17087

동생 N명과 숨바꼭질을 하면서, 한번에 X만큼 움직일 수 있다고 할때, 한번에 움직이기 위한 값을 구하는 문제이다.

---

이번 문제에서 중요한 것은 GCD이다. 즉, 최대공약수를 구해야 한다는 것.

 

왜 최대공약수가 필요하냐면 한번에 이동할 수 있는 위치값을 찾아서, 동생들의 위치에 모두 도달해야 하기 때문이다.

즉, 수빈이의 위치 - 동생의 위치의 절댓값들의 최대공약수를 찾으면 되는 문제이다.

 

GCD함수를 구현하고, 문제를 해석하면 어렵지 않은 문제이다.

 

나는 배열을 사용하긴 했는데, 지금 풀고 나니까 굳이 배열이 없이도 풀 수 있는 문제인 것 같다. 

#include <iostream>
#include <cstdio>
using namespace std;
int nums[100000];

int GCD(int a, int b)
{
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}

int main(void)
{
    int a, b;
    int gcd = 0;
    scanf("%d %d", &a, &b);

    for (int i = 0; i < a; i++)
    {
        scanf("%d", &nums[i]);
    }

    gcd = nums[0] - b;
    if (gcd < 0)
        gcd = -gcd;

    for (int i = 1; i < a; i++)
    {
        if (nums[i] > b)
            gcd = GCD(gcd, nums[i] - b);
        else
            gcd = GCD(gcd, b - nums[i]);
    }

    printf("%d", gcd);
    return 0;
}