[BOJ 1188] 음식 평론가
- 문제풀이
문제
선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.
선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.
예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있는 경우를 생각해보자. 이때는 각 소시지의 크기를 3:1로 잘라서 큰 조각을 평론가에게 하나씩 주고, 남은 조각을 평론가에게 주면 모두 동일한 양을 받게 된다.
소시지의 수와 평론가의 수가 주어졌을 때, 모든 평론가에게 같은 양의 소시지를 주기 위해 필요한 칼질의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100)
출력
첫째 줄에 모든 평론가에게 동일한 양을 주기 위해 필요한 칼질 횟수의 최솟값을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 128MB |
풀이
$N$개의 소시지를 $M$명에게 똑같이 나누어 주어야 한다. 이 문제를 해결하는 가장 직관적인 방법은 소시지를 일렬로 길게 이어 붙였다고 가정하는 것이다.
- 전체 구조 파악: $N$개의 소시지를 하나로 이으면 총 길이는 $N$이 된다. 이를 $M$명에게 나누어 주려면 한 명당 $N/M$만큼의 길이를 가져야 한다.
- 칼질 횟수 계산: 이론적으로 하나의 긴 소시지를 $M$개의 조각으로 나누기 위해서는 $M-1$번의 칼질이 필요하다.
- 중복 케이스 제외: 하지만 우리는 소시지를 실제로 이어 붙인 것이 아니므로, 이미 잘려 있는 부분(원래 소시지와 소시지 사이의 경계)이 칼질해야 하는 위치와 겹친다면 그 지점은 칼질할 필요가 없다.
- 수식 도출: 전체 길이를 $N \times M$으로 치환해서 생각하면, 소시지의 경계는 $M$의 배수마다 나타나고($M, 2M, \dots$), 우리가 잘라야 하는 지점은 $N$의 배수마다 나타난다. 이 두 지점이 일치하는 횟수는 $N$과 $M$의 최대공약수($\text{gcd}$)와 관련이 있다.
결론적으로 필요한 칼질 횟수는 다음과 같다.
\[\text{Result} = M - \text{gcd}(N, M)\]소스코드에서는 n %= m을 통해 $N \geq M$인 경우(모두에게 소시지를 통째로 몇 개씩 먼저 나눠주는 경우)를 처리하고 있지만, 위 공식은 $N$의 크기와 상관없이 항상 성립한다.
소스코드
Github Link : Source Code
참고 알고리즘 : 유클리드 호제법