[백준 1188] 음식 평론가 (C#, C++) - soo:bak

문제 링크

1188번 - 음식 평론가

설명

동일한 소시지 N개를 M명의 평론가에게 정확히 같은 양으로 분배해야 합니다. 각 소시지는 어느 위치에서든 자를 수 있습니다.

이때 필요한 최소 칼질 횟수를 구하는 문제입니다.

접근법

각 평론가는 전체 소시지의 1/M만큼을 받아야 하므로, 전체를 M등분하여 총 M개의 조각이 필요합니다.

단순히 생각하면 M - 1번의 칼질이 필요할 것 같지만, 실제로는 더 적은 칼질로 가능합니다.

g = gcd(N, M)이라 하면 N과 M의 최대공약수로 인해 전체 문제를 g개의 동일한 패턴으로 나눌 수 있습니다.

예를 들어 N = 4, M = 6일 때 g = 2이므로, 2개 소시지를 3명에게 나누는 패턴을 2번 반복하면 됩니다.

각 패턴에서는 N/g개의 소시지를 M/g명에게 분배합니다.

M/g개의 조각이 필요하므로 M/g - 1번의 칼질이 필요합니다.

총 g개의 패턴이 있으므로 전체 칼질 횟수는 g × (M/g - 1) = M - g가 됩니다.

따라서 gcd(N, M)을 구한 후 M - gcd(N, M)을 출력하면 됩니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static int Gcd(int a, int b) {
      while (b != 0) {
        var temp = a % b;
        a = b;
        b = temp;
      }
      return a;
    }

    static void Main(string[] args) {
      var tokens = Console.ReadLine()!.Split();
      var n = int.Parse(tokens[0]);
      var m = int.Parse(tokens[1]);

      var g = Gcd(n, m);

      Console.WriteLine(m - g);
    }
  }
}

C++

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

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

  int n, m; cin >> n >> m;
  int g = gcd(n, m);

  cout << m - g << "\n";

  return 0;
}