[백준 1188] 음식 평론가

www.acmicpc.net/problem/1188

1188번: 음식 평론가

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와 b에서 a를 b로 나눈 나머지를 r이라고 했을 때 a % r이 0이 될 때까지 반복을 해주는 방식으로 최대공약수를 산출하기에 시간 복잡도가 O(Log N)입니다.