백준 1188 - 음식 평론가

www.acmicpc.net/problem/1188

 

평론가들에게 같은 양의 소시지를 주기 위해 필요한 칼질 횟수의 최소를 구하는 문제이다.

 

알아야 할 것들

1. 가능한한 소시지는 칼질하지 않은 상태로 평론가들에게 주는게 최적해에 이를 수 있다. 즉 평론가들에게 칼질 없이 공평하게 소시지를 줄 수 있으면 답은 0이 된다.

 

2. 칼질을 해야 한다면 이 횟수를 줄이기 위해 소시지당 최적의 조각을 찾아야 한다.

 

여기에서 최적화된 소시지 조각을 찾는게 문제 해결의 핵심이다.

 

방법

우선 멀쩡한 소시지를 평가원에게 주고 남은 소시지와 평가원의 최대공약수를 찾는다.

 

남은 소시지를 최대 공약수로 나눠 몇묶음이 나올 수 있는지 regroup을 구한다. 묶인 소시지는 한개의 소시지로 친다.

 

그 다음 심사위원 수를 regroup으로 나눠 묶인 소시지 당 일정한 평가원을 배정하도록 한다.

 

융합된 소시지에 칼질을 내는 횟수에 regroup을 곱해주면 답이 출력된다.

 

 

증명?

묶인 소시지를 한개로 치면 나뉜 부분이(5개를 묶으면 4부분으로 나뉜 한개의 소시지로 볼 수 있다.) 정답에 영향을 주는게 아니냐 하는 의문이 생길 수 있다.

 

묶인 소시지에다 평가원을 배정하면 이 소시지의 개수와 평가원의 수는 서로소가 된다.

 

즉 이미 나뉜 부분을 공유하면서 소시지를 공평하게 자르는 방법은 존재하지 않는다.

 

따라서 소시지를 한 묶음으로 만들면서 생기는 조각은 무시해도 된다.

 

전체 코드

#include <iostream>

using namespace std;

int res;

inline int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }

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

    int remainder = n % m;

    if (!remainder)
    {
        cout << 0;
        return 0;
    }

    int regroup = gcd(remainder, m);
    int transfer = m / regroup;
    res += regroup * (transfer - 1);

    cout << res;
}