[BOJ 1188] 음식 평론가

BOJ 1188 음식 평론가

유형

• 수학

풀이

수학적인 문제라고는 생각하지만 풀이를 생각해보아도 예외가 없는 방법이 떠오르지 않아서 다른 사람들의 풀이를 참고하였다.

쉽게 생각해서 n을 하나의 덩어리라고 생각했을 때 m개로 나누려고 하면 m-1번 자르면 된다. 이 문제에서는 길이가 1인 n개로 이미 나누어져있기 때문에 n과 m의 최대 공약수 부분에서는 자르지 않아도 된다.

여기까지만 생각하면 구현은 아주 간단했다. m번 자를 때 gcd(n, m)번은 이미 잘려있기 때문에 그만큼 빼주게 되면 정답을 얻을 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int n, m;

int gcd(int x, int y) {
	while (y != 0) {
		int temp = y;
		y = x % y;
		x = temp;
	}
	return x;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m;

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

	return 0;
}