[백준] 1188번: 음식평론가(구현, 최대공약수)

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

1188번: 음식 평론가

코드

import java.util.Scanner;

public class Main {
	public static int GCD(int a, int b) {
		if(b == 0)	return a;
		return GCD(b, a%b);
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();
		int M = scan.nextInt();
		System.out.println(M - GCD(N, M));
		scan.close();
	}

}

풀이

이 문제는 풀이만 알면 정말 간단하지만,, 그 풀이를 생각해내는게 어렵다.

처음에 풀때는 N과 M을 기준으로 N>M , N==M , N<M 으로 나누어서 풀었는데,

풀다보니까 두 수가 서로 배수인지 아닌지에 대해 관련이 있었다.

또한 소시지를 이어붙이는 방식에 대해 생각을 못했었다.

갯수와 상관없이 평론가들은 소시지를 N/M 개 만큼 가져간다.

 

N = 3 , M = 5 ---> 1명당 가지는 소시지의 수 = 3/5    --- 필요한 칼질 : 4회

N = 4 , M = 5 ---> 1명당 가지는 소시지의 수 = 4/5    --- 필요한 칼질 : 4회

N = 6 , M = 3 ---> 1명당 가지는 소시지의 수 = 6/3    --- 필요한 칼질 : 0회 

 

여기서, 소시지 N개를 이어붙이면 칼질은 (M-1)번이 필요하다.

하지만 마지막과 같이, N이 M의 배수일경우 칼질은 전혀 필요가 없다.

즉 최소한 M - GCD(N, M)번의 칼질이 필요하다.

(최악의 경우 GCD(N, M) = 1 ---> (M-1)번의 칼질)