[BOJ] 1188. 음식 평론가

생각하기 어려운 수학문제였다.

단순히 생각해서 N개의 소세지를 전체 이어붙이고 M개로 만들기 위해선 (M-1)번의 칼질이 필요하다는 것을 알 수 있다. 하지만 N이 M으로 나눠지거나 M이 N으로 나눠지는 경우 생각하지 않아도 되는 칼질의 경우가 생기는 것을 알 수 있다. 이것을 위해 최대공약수로 나누어 답을 구한다면 (M/GCD - 1) 번의 칼질이 나오는데 이것을 다시 GCD로 곱해야지 최종 답을 알 수 있다.

즉, 칼질횟수 = GCD(M/GCD - 1) = M - GCD 임을 알수가 있다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1188_음식평론가 {
    static int N,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());
        int GCD= gcd(N,M);
        System.out.println(GCD*(M/GCD-1));
        
    }
    
    
    static int gcd(int a,int b) {
        if(b==0)
            return a;
        
        return gcd(b,a%b);
    }
}