백준 1188번 음식 평론가

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

평론가들은 일인당 소시지 N/M 개의 소시지를 가져갑니다.

즉, 소시지를 N개 이어붙일 경우 (M - 1)번의 칼질이 필요합니다.

하지만, N이 M으로 나누어 떨어질 경우에는 칼질이 전혀 필요없습니다.

따라서, M - GCD(N, M)번의 칼질이 필요합니다.(최악의 경우 GCD(N, M) = 1이기 때문에 (M - 1)번의 칼질)

#include <iostream>

using namespace std;

 

//최대 공약수

int GCD(int a, int b)

{

        if (a%b == 0)

                 return b;

 

        return GCD(b, a%b);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, M;

        cin >> N >> M;

 

        cout << M - GCD(N, M) << "\n";

        return 0;

} 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~