백준 14490번 백대열 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 14490 백대열

14490 백대열 문제

출처

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

14490번: 백대열

저번 포스트에 작성한 알고리즘과 비슷한 분류이다. 최대공약수를 구해야 하는 문제로 두 수를 약분하여 출력하면 된다.

math.gcd 라이브러리를 활용하는 방법은 전 포스트를 확인하시면 됩니다. - 이전 발행 글보기

 

알고리즘 분류

• 수학
• 문자열
• 정수론
• 파싱
• 유클리드 호제법

---

소스코드 

n, m = map(int, input().split(':'))

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

t = gcd(max(n, m), min(n, m))
print(f'{n // t}:{m // t}')

---

풀이

이번 글에서는 유클리드 호제법 설명도 추가하여 풀이하려고 한다.

 

유클리드 호제법

최대공약수를 구하는 알고리즘 중 하나로 상당히 간단하다. 

 

왼쪽의 그림처럼 두 수 A, B를 나눈 나머지가 (A % B) = 0이 될 때까지 (B, A % B)를 계산하며 값을 구하는 알고리즘이다.

예를 들어 1071, 1029의 최대공약수를 구하기 위해서는

(1071, 1029) -> (1029, 42) -> (42, 21) -> (21, 0)

의 순서를 거치고 21이 최대공약수인 점을 확인할 수 있다.

이를 하드코딩 즉 함수로써 작성하면 while문을 통해 (a, b) 중 b가 0일 때 a가 최대공약수이므로 조건을 만족할 때 a 값을 출력하도록 한다. 0이 아니라면 재귀 함수를 사용하여 다시 같은 풀이를 거친다. 

 

이 문제에서 주의해야 할 점은 유클리드 호제법을 사용할 때 gcd함수는 a가 두 값 중에 큰 값, b는 두 값중 작은 값이 들어가야 정확한 풀이가 가능하다는 점이다.

:를 포함한 출력은 위의 방식 이외에도 ('%d:%d' %(n // t, m // t)) , ('{}:{}'.format(n // t, m // t)), (n // t, m // t, sep=':')

다양한 방법으로 출력할 수 있다.

---

풀이 결과