[BOJ] 15979 - 스승님

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

BOJ - 스승님

문제 유형: 수학, 애드혹, 정수론, 유클리드 호제법

문제 난이도: Silver II

시간 제한: 1초

메모리 제한: 512MB

 

문제

현욱은 옛날 자신에게 알고리즘을 가르쳐 준 스승님이 어느 신비로운 밀림 속 나무 아래에서 수행 중이라는 사실을 전해 들었다.

이 무한한 넓이의 밀림에는 모든 격자점(x, y 좌표가 모두 정수인 위치)마다 완전히 똑같은 모양의 나무가 한 그루씩 심어져 있고, 현욱의 스승은 그 중 (M,N) 좌표의 나무 아래에서 수행을 하고 있다.

이 밀림에는 또 다른 특징이 있는데, 어떤 나무 아래에서 볼 수 있는 다른 나무로 순간이동을 할 수 있다는 것이다. 어떤 나무 아래에서 다른 나무를 보려면, 그 두 나무의 좌표를 잇는 직선을 그었을 때 중간에 다른 나무가 존재하지 않아야 한다. 

예를 들어, 현욱이 (0, 0) 위치에 있을 때 (1, 1) 위치에 있는 나무 혹은 (1,2) 위치에 있는 나무는 볼 수 있기 때문에 바로 순간이동 할 수 있다. 하지만 (2, 4) 위치에 있는 나무는 (1, 2) 위치에 있는 나무에 가려 보이지 않으므로 바로 순간이동 할 수 없다.

현욱은 수행을 돕기 위해 스승님이 있는 곳으로 가려고 한다. 하지만 밀림의 신비로운 기운으로 인해 나무 사이를 걸어서 이동하는 것은 위험할 수 있어서, 현욱은 순간이동만 이용해서 (M, N) 위치로 이동할 것이다. 또, 순간이동은 할 때마다 멀미가 심하게 나기 때문에 현욱은 최대한 적은 횟수만큼만 순간이동을 사용해서 (M, N) 위치로 이동하려고 한다.

이 밀림에 들어오는 모든 사람은 저절로 (0,0) 위치에 있는 나무 밑으로 이동하게 된다. 현욱을 도와 (0,0) 위치의 나무 아래에서 (M, N) 위치의 나무 아래로 이동하는 데 필요한 최소 순간이동 횟수를 구해보자.

 

입력

첫째 줄에 현욱의 스승이 있는 위치를 나타내는 두 정수 M, N이 주어진다.

 

출력

첫째 줄에 (M, N) 좌표로 이동하기 위해 필요한 최소 순간이동 횟수를 출력한다.

 

풀이

만약 m == n == 0인 경우, 답은 0이다.

만약 gcd(m, n) == 1인 경우, 답은 1이다. 둘이 서로소인 경우, 바로 이동가능하다.

만약, gcd가 1이 아닌 경우, 두 서로소 쌍 a, b에 대해, 임의의 점(a, b)로의 이동을 1번만에 가능하다. 

그리고, (a, b)에서 (m-a, n-b)로 1번만에 이동 가능할 수도 있다.

즉, a, b가 서로소이고, m-a, n-b가 서로소인 임의의 정수 쌍(a, b)는 반드시 존재한다.

따라서, 2번 이내로 가능하다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

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

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    n = abs(n);
    m = abs(m);

    if (n == 0 && m == 0) {
        cout << "0\n";
    } else if (gcd(n, m) == 1) {
        cout << "1\n";
    } else {
        cout << "2\n";
    }

    return 0;
}