[백준 1188번] 음식 평론가 (C++)

문제링크 : https://www.acmicpc.net/problem/1188

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    
    cout << M-gcd(N, M);
    return 0;
}

 

최대공약수를 써야한다는 것은 알았지만, 정확히 이해가 가지 않아 시간이 소요된 문제이다.

 

먼저 m개를 n명에게 배분해야 하기에 소세지를 m/n을 하여 배분하면 된다.

하지만 나누어 떨어지지 않는 경우는 잘라야 하는 필요성이 생긴다.

따라서 gcd(N, M)을 구해 가능한 만큼 그룹을 나눠주고 시작한다.

여기서 각 그룹의 인원 수는 m/gcd(N, M)이다.

추가적으로 해당 그룹 인원 수를 자르는 횟수는 m/gcd(N, M)-1이다.

근데 나눈 그룹과 각 자라는 횟수는 gcd(N, M)개 만큼 있으므로, 최종적으로 gcd(N, M) * (m/gcd(N, M)-1)이 된다.

이를 풀어서 써주면 M-gcd(N, M)이다.

예시 : N=8, M=12
gcd(N, M) = 4

그룹 나누기 
n/gcd(N,M) = 2
m/gcd(N,M) = 3

3 3 3 3
2 2 2 2

그룹 (3, 2)에 대해 잘라야 하는 횟수는 2번 
(기본 2개를 1명한테 주면 나머지 2명에게 줄 것이 필요 -> 2개 빵을 2번 나눠서 공평하게 분배)
이러한 그룹이 4개(gcd(N,M)임
따라서 정답은 2*4