알고리즘/구현

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

잉읭응 2020. 5. 3. 16:40
반응형

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

 

1188번: 음식 평론가

문제 선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다. 선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다. 예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네

www.acmicpc.net

 

소시지를 하나로 이어붙인 상태 즉, 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;
}

 

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

반응형