[백준/Python] 1735번 분수 합 문제

■ 1735번 분수 합 문제

 

출처: 백준 1735번 분수 합 문제

 

 

■ 코드 풀이 (44ms)

 

기약 분수는 분자와 분모의 공약수가 없는 상태입니다. 우선 분자(top)와 분모(bottom)의 최대 공약수가 있는지 유클리드 호제법을 통해 빠르게 확인합니다. 최대 공약수가 없다면, 기약 분수를 의미하므로 break로 while문을 탈출합니다.

최대 공약수가 있다면, 아래 코드에서 else 구문을 진행합니다. 분자와 분모가 동시에 2로 나누어지지 않을 때까지 계속 2로 나누어 줍니다. 분자와 분모가 2로 나누어지지 않는 경우에는 1씩 증가(i+1)시켜서 위의 과정을 반복합니다.

유클리도 호제법에 대해 모르시는 분들을 위해 코드 아래에 링크 넣어 두었으니, 참고하셔서 공부하시면 될 것 같습니다.

A,B = map(int, input().split())
C,D = map(int, input().split())

top = A*D + C*B
bottom = B * D

i = 2 
while max(top, bottom) != 1:
    max_value, min_value = max(top, bottom), min(top,bottom)
    
    #유클리드 호제법
    while min_value != 0:
        max_value = max_value%min_value
        max_value,min_value = min_value, max_value 
    
    if max_value == 1:
        break

    else:
        if (top%i == 0) and (bottom%i==0):
            top /= i
            bottom /= i
            continue
        i += 1
    
print(int(top), int(bottom))

 

[백준/Python] 1934번 최소공배수 문제

[백준/Python] 1934번 최소공배수 문제