백준 1188 - 음식 평론가

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

1188번: 음식 평론가

칼질 하는 횟수를 어떻게 구해야 할까?

 

4개의 소세지와 6명의 평론가가 있다고 해보자.

모든 소세지를 한 줄로 연결한다.

빨간 선은 모른 척 합시다

이제 이 소세지를 6명의 평론가에게 나눈다. 전체 길이를 6으로 나눠 해당 길이마다 칼질을 하면 된다.

 

맨 마지막 부분은 칼질할 필요가 없다. 그림이 조금 부정확하지만 3번째 칼질할 곳도 원래 서로 떨어져 있는 소세지이므로 칼질할 필요가 없다.

 

정리하면, 전체를 N등분한 구간과 M등분한 구간 중 일치하지 않는 구간의 개수를 찾으면 된다. 이때 '전체'는 N과 M등분이 가능해야 하므로 N과 M의 최소공배수가 되겠다.

 

코드 보기

//S : 소세지 수 N, P : 사람 수 M
void solve(int S, int P) {
	//checked[i] : i와 i+1번째 조각 사이가 잘려있는 지 여부, 즉 N등분 된 구간인가

	int cut = 0, sz = lcm(S, P), i;
	
	vector<bool> checked(sz);
	int Sinterval = sz / S;
	for (i = Sinterval; i < sz; i += Sinterval)
		checked[i] = 1;

	int Pinterval = sz / P;
	for (i = sz - Pinterval; i > 0; i -= Pinterval) {	//맨 끝 구간은 제외
		if (!checked[i])
			cut++;	//N등분 된 구간이 아닐 경우 칼질
	}

	cout << cut << endl;
}