1188 음식 평론가

사람과 소시지의 최대공약수를 응용한 문제다. 만일 소시지가 4개, 사람이 6명이라면 결국에는 소시지 2개를 사람 3명이서 나눠야 된다고 생각할 수 있다. 4개, 6명에서 2개, 3명으로 줄이는 과정은 최대공약수로 나눴다는 점이다. 2개와 3명은 더이상 나눌 수 없기 때문에, 3명에서 나누기 위해서는 3-1번 조각을 내어야만 한다

 

이를 수식으로 작성하면 result = gcd * (m/gcd - 1) = m - gcd가 된다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/1188.cpp

 

	#include <iostream>
	using namespace std;
	int gcd(int a, int b) {
	if (b == 0) {
	return a;
	}
	return gcd(b, a % b);
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	cout << m - gcd(n, m) << '\n';
	return 0;
	}

view raw 1188.cpp hosted with ❤ by GitHub