BOJ 1188 : 음식 평론가

• 문제 링크 : boj.kr/1188
• 난이도 : G4
• 태그 : 정수

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

ll gcd(ll a, ll b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    cout << m - gcd(m,n);

    return 0;
}

---

풀이

소세지를 일렬로 늘어놓는다. 일렬로 늘어놓은 소세지를 한 덩어리로 생각해 길이가 N인 큰 소세지를 M등분 한다고 생각할 수 있다. 이러면 칼질을 M-1번 하게 된다.

편의상 M번째의 덩어리를 만드는 칼질도 포함하여 M번의 칼질을 한다고 하자. 이 칼질 중 정확하게 소세지의 경계를 자르는 칼질이 포함될 것이다. 이 칼질은 실제로는 소세지를 자르지 않기 때문에 필요한 칼질의 수에 포함되지 않는다.

경계를 자르는 칼질의 수를 구해보자.

전체의 길이를 NM이라고 하자. 소세지의 길이는 각각 M이고, 소세지의 경계는 {M, 2M, 3M, ... , NM}이다.

칼질의 간격은 각각 N이고, 칼질의 위치는 {N, 2N, 3N, ... , MN}이다. 이 두 집합의 교집합의 수는 경계를 자르는 칼질의 수이며 gcd(N, M)과 같다.

따라서 실제 칼질의 수는 M-gcd(N,M)이다.