[백준] 1188번 - 음식 평론가 (C++) 문제 및 풀이

문제) 백준 - 수학 - 음식 평론가

-> https://www.acmicpc.net/problem/1188

1188번: 음식 평론가

 

예제와 n과 m의 경우의 수를 관찰하며 해결했다.

소시지를 하나로 이어 붙인다. n개의 소시지를 무조건 m명의 평론가한테 주려면 소시지를 최대 m-1번 잘라 m개의 배수개로 토막 낸다. n과 m이 서로소일 때는 m - 1번 자르는 것이 답임을 알 수 있고, 서로소가 아닐 경우에는 m - 1번에서 n-1번 잘린 위치와 m - 1번 잘린 위치의 공통 위치만큼 제외해준다. 이 수는 최대공약수임을 알 수 있다.

 

 

 

C++ 소스코드)