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

1188번: 음식 평론가

 

문제

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

1188번: 음식 평론가

 

 

풀이

소시지의 개수 N과 평론가의 수 M을 입력받고 소시지 N개를 모두 균등하게 나누어 평론가 M명에게 같은 양을 나누어 준다. 이때 소시지를 자르는 횟수를 구하는 문제다.

 

소시지를 일자로 세우고 M등분하면 된다. 이때 칼질의 횟수는 M-1번이 된다. 그러나 이미 소시지는 N개를 일자로 나열한 것이므로 N등분되어있다. 따라서 중복으로 잘리는 횟수를 구해 빼주면 된다. 중복인 칼질의 수는 (N과 M의 최대공약수) - 1 이므로 정답은 M - gcd(N, M)이다.

 

 

코드

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

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  cout << m - gcd(n, m) << '\n';
  return 0;
}