[JAVA] 백준 1188번 : 음식 평론가

 

- 코드

   - 많은 경우의 수를 고려했을 때 해결책은 평론가 수 - (소시지 수와 평론가 수의 최대공약수)로 나왔다. 

   - 최대공약수를 구하는 것을 재귀로 하려고하다가 재귀로하면 시간이 오래 걸린다는 말을 들어서 반복문으로 해결했다.

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
		
    	int cutting = 0;

    	while (true) {
    		n = n % m;
    		
    		if (n == 0)
    			break;
    		if (m%n == 0)
    		{
    			cutting += (m / n - 1)*n;
    			break;
    		}
    		else {
    			cutting += (m / n)*n;
    			m = m % n;
    		}
    	}
    	
    	System.out.println(cutting);
	}
}