(Python/🥇5)백준알고리즘 1188번:음식 평론가

문제 바로가기 

문제:

선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다. 선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다. 예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있는 경우를 생각해보자. 이때는 각 소시지의 크기를 3:1로 잘라서 큰 조각을 평론가에게 하나씩 주고, 남은 조각을 평론가에게 주면 모두 동일한 양을 받게 된다. 소시지의 수와 평론가의 수가 주어졌을 때, 모든 평론가에게 같은 양의 소시지를 주기 위해 필요한 칼질의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100)

출력:

첫째 줄에 모든 평론가에게 동일한 양을 주기 위해 필요한 칼질 횟수의 최솟값을 출력한다.

 

풀이:

생각을 아주 많이 한 문제..

 

 

import sys
from math import gcd

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n,m = map(int,sys.stdin.readline().rstrip().split(" "))
print(m - gcd(n,m))

크기는 n / m  이여야지 똑같은 크기 만큼 가지는 것이다.

즉 나누어 떨어지면 안 잘라도 된다. 예를들면 6, 2 와 같은경우는 안 잘라도 된다. 개인당 3개씩 가져가면 되니깐 

 

하지만 3, 4 같은 경우 는 개인당 3/4 만큼 가지고 있어야 한다.

3개의 소세지를 한개로 만들어본다  ㅡㅡㅡ 이렇게 

최악의 경우에는 m - 1 번인 3번을 잘라서 3/4 만큼 가지게 해야한다.

즉 평론가 수 - gcd(n,m) 을 해주면 된다.

 

 

다른 예를 들어보겠다. n = 4, m = 10 일경우

하나의 소세지라고 생각해 준다. gcd(4,10) = 2 , 10-2 = 8 로 8개 가 된다.

n >  1개당 2번씩 자른다는 것이다.

 

설명이 하찮다 이해가 잘 되지 않는다면

https://physics-07.tistory.com/10

백준 1188: 음식 평론가

이분을 참고해도 좋을 것 같다.