[백준] G5 1188번 음식 평론가 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1188번: 음식 평론가

[문제] 

선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.

선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.

예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있는 경우를 생각해보자. 이때는 각 소시지의 크기를 3:1로 잘라서 큰 조각을 평론가에게 하나씩 주고, 남은 조각을 평론가에게 주면 모두 동일한 양을 받게 된다.

소시지의 수와 평론가의 수가 주어졌을 때, 모든 평론가에게 같은 양의 소시지를 주기 위해 필요한 칼질의 수를 구하는 프로그램을 작성하시오. 

[입력]

첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100)

[출력]

첫째 줄에 모든 평론가에게 동일한 양을 주기 위해 필요한 칼질 횟수의 최솟값을 출력한다. 

 

 

---

[풀이]

1. 소시지를 자르는 횟수는 평론가의 수 - 소시지의 수와 평론가의 수의 최대 공약수이다.

2. 최대공약수를 구해주고 m에 뺀 결괏값을 출력해주면 된다.

[접근]

1. 소시지를 자르는 횟수에 대한 접근을 어떻게 해야 할지 모르는 상태로 문제에 접근했다.

2. 소시지를 n, 평론가를 m으로 두었을 때, 평론가가 받을 수 있는 소시지의 양은 n/m이다.

3. 여기서 소시지를 한 줄로 연결했을 때, 총 m - 1번의 칼질을 하면 된다.

4. 하지만 n이 m의 배수일 경우는 자르지 않아도 된다.

5. 최소 칼질은 m - gcd(n - m)가 된다.

[코드]

package BOJ_gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_G5_1188 {
	static int n; // 소시지 수
	static int m; // 평론가 수

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		// 평론가 수 - 최대 공약수
		System.out.println(m - gcd(n, m));
	}

	// 최대 공약수
	public static int gcd(int a, int b) {
		while (b > 0) {
			int temp = a;
			a = b;
			b = temp % b;
		}

		return a;
	}
}