[백준] 1188 음식 평론가(Java)

백준 - 1188 음식 평론가

풀이

1. n / m 이 나누어 떨어지면 자를 필요 없음 -> 0
2. n / m 이 나누어 떨어지지 않으면 m - gcd(n, m)

(왜 이런 결과가 나오는 지 잘 모르겠고, 그냥 규칙을 찾아보니 이렇게 됨...)

코드

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

public class FoodCritic {
	public static void main(String[] args) throws IOException {
		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());

		System.out.println(m - gcd(n, m));
	}

	private static int gcd(int a, int b) {
		int c = a % b;
		if (c == 0) return b;
		return gcd(b, c);
	}
}