Baekjoon 8682번 Happy monkey

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, d;
        cin >> n >> d;
        cout << n/gcd(n,d) << "\n";
    }
    return 0;
}

둥글게 배치된 동물원의 우리(cage) 위에서 원숭이가 뛰어내리며 문을 열어준다. 우리의 개수 n 과, 한번 점프하여 이동할 수 있는 거리 d 가 주어질 때 탈출을 돕는 동물의 최대수를 구하여야 한다. 단, 우리 안의 동물은 각각 한 마리뿐이며 이미 열려있는 우리 위로는 점프하지 않는다.

예제를 몇개 풀면서 최대공약수를 이용한 규칙을 찾아 풀이하였지만, 왜 최대공약수 개념이 사용되는지 이해가 되지 않아 조금 더 공부해보았다.