BOJ 1188 - 음식 평론가

www.acmicpc.net/problem/1188

1188번: 음식 평론가

 

 

이 문제는, 최대 공약수를 활용하는 문제이다.

N 개의 소시지들을 한 줄로 다 이어 붙인다고 생각해보면

M 명에게 동등한 양을 주기 위해서는 N / M 개 만큼 줘야한다.

그러나 예외 사항으로, N 이 M 으로 나눠 떨어진다면 자를 필요가 없다 (ex) N = 6, M = 6

M - gcd(N, M) 을 하면 이에 대한 답을 구할 수 있다.

 

 

최대 공약수를 쓴다는것을 생각해내기는 꽤나 어려운것 같아서 쉬운 문제는 아닌것 같다

 

 

- c++

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