백준/골드
[백준 1188번] 음식 평론가 (C++)
게임개발기원
2025. 4. 28. 05:11
문제링크 : 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