[백준][C++] 1188: 음식 평론가

문제

1188번: 음식 평론가

풀이

수학, 유클리드 호제법

 

소시지를 일자로 이어붙였을 때, M등분 하기 위해서는 길이가 N / M이 되도록 잘라야 한다. 이를 위해선 총 M - 1번 잘라야 한다. 소시지는 일자로 이어붙인 상태이므로, 이미 잘려진 부분이 존재한다. 이 잘려있는 부분이 M - 1번 자른 부분과 동일한 경우, 해당 부분은 자른 횟수에서 제외해야 한다. 이 동일한 부분은 (N과 M의 최대공약수 - 1)개 이다. 

 

N = 5, M = 15

N이 5, M이 15인 경우, 소시지 하나는 3조각으로 나눠진다. 이 때, 조각 하나의 길이는 1/3이다. 총 잘려지는 횟수는 14번 이며, 이 중 겹치는 부분은 4번이다. 총 10번이 잘려진다.

코드

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }

    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

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

    int N, M;
    cin >> N >> M;

    // 소시지를 일자로 이어붙인 다음, 평론가에게 동일한 양을 주려면 N / M 등분해야 한다.
    // 그러므로, 결과적으로 소시지는 (M - 1)번 잘려야한다.
    // 소시지는 일자로 이어붙인 상태이므로, 이미 잘려있는 부분이 있다.
    // 이 잘려있는 부분이 (M - 1)번 자른 위치와 동일한 경우는 해당 부분은 횟수에서 제외해야 한다. 
    // 이 동일한 부분은 (N과 M의 최대공약수 - 1)개 있다.
    // 그러므로, 정답은 아래와 같다.
    cout << (M - 1) - (gcd(N, M) - 1);

    return 0;
}