[문제 출처 : Codechef] 이번에 살펴볼 문제는 우리가 이미 다뤘던 최대공약수 구하기를 활용하여 풀 수 있는 예제입니다. 그럼 어떤 문제인지 살펴봅시다.
한 부대에서 취사병이 음식을 준비합니다.
군대에서 최대한 많은 병사들을 먹여야 하기 때문에 이 취사병은 최대한 많은 접시의 음식을 만들어야 합니다.
모든 재료를 하나 이상씩 사용하되, 재료들을 각각 자연수 개수만큼씩만 사용하여 음식을 만든다고 합니다.
그러면 이 취사병이 제일 많은 음식 접시를 만들었을 때, 각 음식 접시가 포함하고 있는 각 재료의 수는 어떻게 될까요?
즉, 예를 들면 각 재료가 [1, 2, 3]만큼 있다고 하면, 취사병이 만들수 있는 접시는 총 1접시입니다. 그리고 그 한 접시에 재료를 [1, 2, 3]만큼씩 사용합니다. 왜냐하면 자연수 개수의 재료를 사용해야 하기 때문이죠. 그러면 만약 재료가 [2, 4] 만큼 있다면, 접시당 [1, 2]씩 사용하여 2접시를 만들 수 있고, [2, 4]씩 써서 1접시를 만들 수도 있습니다. 최대한 많은 접시를 만들어야 하기 때문에 2접시를 만들 때, [1, 2]만큼 재료를 쓰므로 답은 [1, 2]가 됩니다.
이 문제의 KEY는 결국 최대 접시의 수가 모든 재료들의 최대공약수와 같다는 것을 인지하는 것입니다! 앞서 최대공약수 구하기에서 구현했던 두 수의 최대공약수를 찾는 코드를 가져오겠습니다.
#유클리드 호제법을 사용한 최대공약수 찾기 알고리즘
def findGCD(i, j):
if i > j:
i, j = j, i
while j % i != 0:
k = j % i
j = i
i = k
return i그리고 각 재료들을 하나씩 집어서 recursive하게 최대공약수를 구해나가면 최종적으로 나온 최대공약수가 최대 접시 수가 됩니다 :) 그러므로 각 재료를 최대 접시 수로 나눠준 것이 결국 우리가 원하는 답이 되겠지요?
def leastIngrPerDish(ingredients):
#재료가 하나인 경우는 그 재료 개수만큼 접시를 만들 수 있습니다.
if len(ingredients)==1:
return 1
#일단 첫 두개의 재료의 최대공약수를 구한 후,
#Recursive하게 계속 최대공약수를 구해나갑니다.
GCD = findGCD(ingredients[0], ingredients[1])
for i in range(2, len(ingredients)):
GCD = findGCD(GCD, ingredients[i])
#결과는 각 재료를 최대 접시 수로 나눠준 것입니다.
return [i/GCD for i in ingredients]
>>> print leastIngrPerDish([4,4])
[1, 1]
>>> print leastIngrPerDish([2,3,4])
[2, 3, 4]
>>> print leastIngrPerDish([3,15,9,6])
[1, 5, 3, 2]