[알고리즘 문제 풀이][유클리드] 백준 3036번 - 링

백준 3036번 링 문제입니다.

(유클리드 호제법 = 최대공약수 구하는 방법)

 

- 문제 설명: https://www.acmicpc.net/problem/3036

- 문제 풀이:

 

본 문제는 맨 왼쪽에, 첫번째로 있는 링이 돌 때 다른 링이 몇 바퀴 도는지를 출력하는 문제입니다.

문제에서 입력으로 주어지는 것은 각 링들의 반지름입니다.

만약에 반지름이 8, 2, 4 순이라면, 원의 둘레는 2πr 이므로, 16 π, 4 π, 8 π 가 됩니다.

그러면 두 원이 동시에 돌아갈 때 첫 번째 원이 1 바퀴 회전한다면 두번째 원이 4바퀴 회전할 것입니다.

 

이 문제에서 원하는 답은 첫번째 원 둘레 / 다른 원의 둘레가 될 것입니다.

이를 문제의 출력 형식인 기약 분수 형태로 출력한다면, 4/1, 2/1 이 될 것입니다.

 

첫번째 원의 반지름 (둘레는 2π 만 곱해진 것이므로 다 나눴다고 생각하고 무시해도 됩니다) 을 분자로, 다른 원의 반지름을 분모로 하면 되지만 문제는 기약 분수를 어떻게 구할 것인가가 됩니다.

기약 분수를 구하기 위해서는 분모와 분자의 최대 공약수를 구해야합니다.

우리가 어릴 때 배운 최대 공약수 구하는 방법대로 한다면 공통된 수를 찾아 나눠가면서 구해야겠지만, 컴퓨터에게 시키려면 1부터 N 까지 다 확인하면서 일일히 공통적으로 나눠지는지 확인해야할 것입니다.

본 문제는 N 이 100개, 숫자 범위가 1000 이므로, 이렇게 풀어도 1초 시간 제한 안에 들어올 것 같습니다.

 

하지만 본 문제를 더 최적화된 방식으로 풀기 위해서는 최대공약수 (=GCD = Greatest Common Divisor) 를 빠르게 구하는 방법을 쓸 수 있습니다. 유클리드 호제법을 이용하면 최대공약수를 빠르게 찾을 수 있습니다.

 

gcd(m,n)이 두 양의 정수 m과 n의 최대공약수라고 하면
gcd(m,n)=gcd(n, m mod n)이 성립한다는 것이다. (여기서 m mod n은 m을 n으로 나누고 남은 나머지를 뜻한다.)

[설명 출처] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vivian2323&logNo=220115848284

 

이 방법을 이용하여 48과 18의 최대 공약수를 구해보겠습니다.

gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6 이 됩니다.

이렇게 n자리가 0이 되었을 때, m자리 수가 최대공약수가 됩니다.

 

이를 이용하면 기약 분수를 빠른 시간 안에 구할 수 있습니다.

 

※ 유클리드 호제법 (互除法, Euclidean algorithm) 의 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타냅니다.

[출처] https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

 

※ 유클리드 호제법을 연습하기 좋은 다른 문제 (14490번 - 백대열)

https://www.acmicpc.net/problem/14490

- 코드: 

def gcd(m, n):
    if n == 0: return m
    return gcd(n, m % n)

N = int(input())
numbers = list(map(int, input().split()))

for i in range(N-1):
    g = gcd(numbers[0], numbers[i+1])
    print(f"{numbers[0]//g}/{numbers[i+1]//g}")

 

삼항 연산자를 이용하여 gcd 함수를 더 짧게 표현할 수도 있습니다.

def GCD(a,b): return GCD(b,a%b) if b else a

 

- 실수 포인트 & 반례:

가능한 반례

https://www.acmicpc.net/board/view/11577

입력
4
7 12 14 28

출력
7/12
1/2
1/4

 

추가적인 반례
https://www.acmicpc.net/board/view/33802