www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net import math N,M = map(int,input().split()) gcd = math.gcd(N,M) print(M-gcd) 풀이 소시지를 하나로 다 이어붙인다면 n=1일 때 m-1번 잘라야 같은 크기의 소시지로 나눠진다. N,M의 최대공약수를 구하면 [최대공약수-1]이 소시지를 이어붙였을 때 이미 잘려있는 횟수가 된다. 최악의 경우 최대공약수가 1일때 이미 잘려있는 수는 0회 이므로 m-1 이 답이된다. 즉 M - gcd(N,M) 가 답이다. 시간복잡도 유클리드 호제법을 사용한다면 비교대상의 두 수 a..