Algorithm with Math - GCD, LCM (최대 공약수, 최소 공배수)

Algorithm with Math - GCD / LCM

최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수

최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

문제: Mask States

방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다. A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요? (휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)

 

풀이 방법은 다양하지만, 이 문제에서 최소 공배수를 떠올릴 수 있다면, 더 쉽고 빠르게 문제를 해결할 수 있습니다.

A, B, C의 작업 시간과 쉬는 시간 5분을 더하면 A, B, C는 각각 60분, 75분, 90분마다 마스크를 만듭니다.

세 명이 동시에 휴식을 취하는 시점은 세 명이 쉬고 난 직후가 같을 시점이 됩니다.

따라서 쉬고 난 직후가 처음으로 같을 시점을 구해야 하므로 공배수와 최소 공배수의 개념을 알아야 합니다.

 

결과적으로, LCM(60, 75, 90)은 900입니다. (LCM; Least Common Multiple, 최소 공배수)

 

A는 B, C와 휴식을 취한 직후가 처음으로 같을 시점까지 900/60 = 15 번 작업하고, 15번 X 9개 = 135개를 만듭니다.

B는 900/75 = 12번의 작업을 반복하고 12턴 X 15개 = 180개,

C는 900/90 = 10번의 작업을 반복하고 10턴 X 25개 = 250개의 마스크를 만들어 냅니다.

 

따라서, A, B, C가 하루에 제작한 마스크의 총 개수는 135개 + 180개 + 250개 = 565개가 됩니다.

 

문제: 조명 설치

이 문제에서 필요한 전구의 개수를 구하려고 할 때, 최대 공약수를 떠올리면 빠르게 문제를 해결할 수 있습니다.

모든 조명을 일정한 간격으로 설치해야 하므로, 가로변과 세로변의 공약수를 구해야 합니다.

가로와 세로 각각 나누어서 나머지가 없이 떨어지는 수들을 나열한 뒤, 공통된 수만 모으면 공약수를 구할 수 있습니다. 그리고 공약수를 기준으로 조명을 설치하면, 가로 세로 길이가 달라도, 일정 간격으로 나눠 조명을 설치할 수 있습니다.

 

최소로 필요한 조명의 개수를 파악해야 하기 때문에 최대 공약수가 필요합니다. 따라서 GCD(12, 24)는 12이고 네 모퉁이는 반드시 설치해야 하므로 각 변의 길이를 최대 공약수 12로 나누어 최소로 필요한 조명의 개수를 구할 수 있습니다.