[boj] 백준 1188 음식 평론가 - 최소 공약수

[문제]

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

1188번: 음식 평론가

 

[풀이]

소세지가 하나로 이어져 있다면 m명의 평론가에게 나누어 주기 위해서는 m-1번 잘라야 한다. 그런데 소세지가 여러개인 경우 이미 잘라져 있는 것이기 때문에 중복된 부분을 제거해야 한다. 예를 들어 3개의 소세지를 6명의 평론가가 나눠먹는다면 둘의 최대 공약수인 3-1=2만큼 이미 잘라져 있는 것이다. 1개로 연결된 소세지였다면 6-1=5번 잘라야 하지만 이미 2번 잘라져있다고 여겨 5-2=3만큼만 더 자르면 된다. 

즉 m-1-(gcd(n,m)-1) = m-gcd(n,m)이 된다. (서로소의 경우 gcd(n,m)은 1이므로 m-1번 자르고, n%m==0인 경우 gcd(n,m)은 m으로 0번 자르는 것이 된다.)

 

[코드]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

int gcd(int n, int m){
    if(n%m==0)
        return m;
    else{
        return gcd(m, n%m);
    }
}

int main() {

    int n, m; //소세지 개수, 평론가 수
    cin >> n >> m; // 3 4

    cout << m - gcd(n, m);
}