[BOJ1188/C++] 음식 평론가

문제 요약

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

1188번: 음식 평론가

m명의 사람에게 n개의 소세지를 공평하게 나눠주려고 할 때, 과연 몇번의 칼질을 해야하는지 생각해보는 문제이다.

오랜만에 보는 수학문제..

입/출력

입출력은 매우 간단하다..(원래 이런문제가 더 어렵다)

 

접근 방식

먼저 예시로 주어진 상황을  먼저 분석했다.

2개의 소세지를 6명이서 나눠먹기 위해서는 각각 1/3조각씩..을 나눠먹는다.. 분수로 생각하니까 이해하기가 너무 어려웠다.

그래서 12(2*6)cm 소세지를 6명이서 나눠먹는다고 생각해보았다. 그러면 한사람이 2cm 씩 먹을 수 있다.

즉 12 cm 짜리 소세지를 6등분, 5번의 칼질을 해야한다는 것이다. 여기까지는 쉽다. 근데 생각해보면 원래 소세지가 2개였으니까 2, 4, 6, 8, 10 이렇게 5개의 위치에서 칼질을 할 때 이미 6은 썰려있다. 그래서 4번의 칼질만 하면 된다.

 

그렇다면 이렇게 하나하나 해보지 않고 내가 자르고 싶은 위치 중 몇 개의 위치가 이미 썰려있어서 칼질을 안해도 되는 위치인지는 어떻게 구할까? -> 여기서 최대 공약수가 필요하다. 왜 최대 공약수인지는 예제를 보면 좀 더 쉽게 이해할 수 있는데, 아까와 같은 방식으로 n=3, m=4 인 경우를 생각해보면 12cm의 소세지를 3번의 칼질로 4등분 해야하는데, 내가 자르고 싶은 위치는 3, 6, 9 이나 원래 소세지는 4, 8의 위치에 분리되어 있어 칼질을 아낄 수 없다.(최대공약수가 1인 경우)

다른 예시로 만약 n=4, m=8인 경우를 생각해보면 32cm의 소세지를 7번의 칼질로 8등분 하는 것이 기본이다. 내가 자르고 싶은위치는 4, 8, 12, 16, 20, 24, 28 이고, 원래 분리되어 있는 위치는 8, 16, 24이다. 4와 8의 최대공약수는 4니까 4-1인 3만큼 칼질을 안해도 된다..! 

 

다른 예시도 생각해보면 알겠지만 결국 우리는 m-1 번의 칼질을 기본으로 하고 있으나 원래 잘린 위치인 (최대공약수-1)만큼 칼질을 하지 않아도 된다는 것을 알 수 있었다. 이제 구현만 하면 끝!

 

아 계산을 간단히 하기 위해서 먼저 거르는 작업도 해줘야 한다.

1. 이미 소세지가 m명에게 균등 분할되는 경우 -> 칼질이 필요 없음!

2. 소세지가 m명 보다 더 많이 있는 경우 -> m명에게 하나씩(두개가 될 수도 있고 그 이상일수도) 돌리고 나머지만 앞에서 했던 방식을 따르면 됨. 

 

최대 공약수를 구하는 알고리즘은 유클리드 호제법을 사용했다.

구현 코드

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	if (n % m == 0) {
		cout << 0;
		return 0;
	}

	if (n > m) {
		n %= m;
	}
	
	int r = m - n;
	while (n % r != 0) {
		int temp = r;
		r = n % r;
		n = temp;
	}

	cout << m - 1 - r + 1;

}