[백준 20003 파이썬] 거스름돈이 싫어요 (실버1, 정수론)

알고리즘 유형 : 정수론(유클리드 호제법)
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
items = [list(map(int, input().split())) for _ in range(N)]
dividend = [i[0] for i in items]

# 공통 분모 구하기
divisor = 1
for _, divider in items:
    divisor *= divider

# 분모 divisor로 맞췄을 때의 분자들로 갱신하기
for i in range(len(dividend)):
    dividend[i] *= divisor // items[i][1]

# 최대공약수 구하는 함수
def findGCD(a, b):
    if a < b:
        a, b = b, a
    
    rest = a % b
    while rest != 0:
        a = b
        b = rest
        rest = a % b
    
    return b

# 분자의 최대공약수 구하기
GCD = dividend[0]
for i in range(1, len(dividend)):
    GCD = findGCD(GCD, dividend[i])

# 현재 result = divisor 분의 GCD
GCD_result = findGCD(GCD, divisor)
print(f'{GCD//GCD_result} {divisor//GCD_result}')

풀이 요약

1. 거스름돈이 발생하지 않기 위해선, 지불하는 코인이 모든 아이템 가격에 대해 약수여야한다.

2. 우선 주어진 아이템의 분모를 공통 분모로 통일해주자.

   1 4
   2 5

   이 경우에

   5 20
   8 20

   이렇게 된다. 이제 이 아이템들의 약수이면서 최대인 수를 구해보자.

3. 정답의 분모는 20으로 고정하고, 정답이 아이템들의 약수여야된다고 했으니, 아이템들의 분자들의 최대공약수를 구하면 된다. 유클리드 호제법으로 구해주자.

4. 구했으면, 이제 분자와 분모의 최대공약수를 분자, 분모에 각각 나눠줘서 기약분수를 만들고 출력하면 된다.

배운 점, 어려웠던 점

• 유클리드 호제법이 핵심인 문제였다.