백준 #17087 숨바꼭질6 문제 풀이 C++

백준 17087 숨바꼭질 6, 실버 1 문제이다.

 

문제의 기본적인 이해는 금방되리라 생각한다.

X-D와 X+D의 위치로 이동할 수 있고, D를 구하는 문제이다.

 

첫 번째 예제를 보면

위치 3에서 위치 1로 이동하려면 2만큼의 이동이 필요하고

1에서 7로 이동하려면 6만큼의 이동이 필요하다

또한 위치 7에서 위치 11로 이동하려면 4만큼의 이동이 필요하다.

수빈이는 1초마다 같은 거리를 움직여야 하기 때문에

한점에서 다른 한점으로 이동한 거리는 모두

가장 작은 이동거리의 배수일 수 밖에 없다.

 

그렇기 때문에 이동한 거리들의 최대공약수를 구하면 그것이 바로 정답이 된다.

 

처음에 문제를 풀때는 

단순히 수빈이의 위치와 동생의 위치 차의 절댓값 중에서

가장 작은 값을 출력했는데, 

이 풀이 방법이 잘 못된 이유는 

최대 공약수가 1인 경우를 생각하지 못해서이다.

 

아래의 코드를 보자

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <numeric>


using namespace std;

vector<int> v;

int main() {
    int n;
    int s;
    int temp;
    cin >> n >> s;
    for(int i = 0; i < n; ++i) {
        cin >> temp;
        v.push_back(temp);
    }
    for(int i = 0; i < n; ++i) {
        v[i] = abs(s-v[i]);
    }
    sort(v.begin(), v.end(), greater<int>());
    temp = gcd(v[0], v[1]);
    for(int i = 2; i < n; ++i) {
        temp = gcd(temp, v[i]);
    }
    printf("%d", temp);
}

C++17에서는 아주 감사하게도 최대공약수와 최소공배수를 구하는 기본함수가 내장되어 있다.

모두 <numeric> 라이브러리에 내장되어 있다.

 

이해를 쉽게하기 위해서 코드를 풀어서 작성했다.

 

먼저 동생의 수와 수빈이의 위치 n,s를 각각 입력받은 후

동생들의 위치를 입력받아 배열에 푸쉬한다.

그 후 동생들의 위치와 수빈이의 위치를 뺀 값의 절댓값을 재할당 해주고

이를 재귀적으로 gcd함수를 호출하여 출력하면 된다.