[백준] 1188-음식 평론가(C++)

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

1188번: 음식 평론가

 

소시지를 하나로 이어붙인 상태 즉, n = 1일때 m - 1번 잘라야 모두에게 같은 크기의 소시지를 줄 수 있다.

 

즉, 최악의 경우 m - 1 최소의 경우 0번이다. 

 

그렇다면 소시지가 여러개가 있을 때 어떻게 해야할까?

 

최대공약수를 생각해보면 답이 나온다. 

 

소시지를 일자로 두고 일정한 크기 만큼 자를 때 두 수의 (최대 공약수 - 1)  만큼 이미 잘려있을 것이다. 

 

즉 식은 b - gcd(a,b) 이다. 

 

 

#include <iostream>
using namespace std;

int n = 0, m = 0;
int GCD(int a, int b) {
	if (a%b == 0)
		return b;

	return GCD(b, a%b);
}

int main() {
	cin >> n >> m;

	cout << m - GCD(n, m) << endl;
}

 

최대 공약수를 구하는 재귀는 위와 같이 구현할 수 있다.