백준 1735번 풀이

문제

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

1735번: 분수 합

분수 두 개의 합을 '기약분수'로 출력하시오

 

풀이

이거는 우리가 초등학생때 배웠던 약분과 통분을 활용해 풀어야 하는 문제이다. 통분은 더할라면 필요하고 약분은 기약분수 만들라면 필요하다. 그러면 뭐 갖고와야 하냐고요?

 

# 알아두면 좋은 유클리드 호제법
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

유클리드 호제법이요.

 

이 문제는 투트랙으로 접근할건데 첫번째로 두 줄에 걸쳐 입력되는 두 개의 숫자가 분자, 분모인 분수 두 개라는 걸 컴퓨터에게 인식시킨 다음 통분해서 더하고, 두번째로 만약 통분해서 더했는데 분자분모가 서로소가 아닐 경우 약분해서 기약분수(분자분모가 서로소인 분수)로 만들거다.

 

n_bunja_1 = bunja_1 * bunmo_2
n_bunmo_1 = bunmo_1 * bunmo_2

n_bunja_2 = bunja_2 * bunmo_1
n_bunmo_2 = bunmo_2 * bunmo_1

sum_bunja = n_bunja_1 + n_bunja_2
sum_bunmo = n_bunmo_1

이거 생각해보니 분모 굳이 두줄로 안 만들어도 될 것 같음. 어차피 통분해서 분모 하나임. 즉, n_bunmo_1과 n_bunmo_2는 같은 수다. 아 메모리 낭비다 그죠... 근데 이걸 내고 글쓰다가 알았음... 아무튼, 분자랑 분모를 계산했다면 통분하고 더하는 절차는 끝난거다. 이제 기약분수 만들자.

 

GCD = Euclidean(sum_bunja, sum_bunmo)

if GCD != 1:
    sum_bunja = sum_bunja // GCD
    sum_bunmo = sum_bunmo // GCD

유클리드 호제법에서 두 수가 서로소일 경우 출력이 1이다. 즉, 두 수가 서로소가 아닐 경우(최대공약수가 존재할 경우) 출력이 1이 아니다. 그러니까 GCD가 1이 아니면 나눠라 이거임.

 

import sys

bunja_1, bunmo_1 = map(int, sys.stdin.readline().split()) # 분수 1호
bunja_2, bunmo_2 = map(int, sys.stdin.readline().split()) # 분수 2호

# 알아두면 좋은 유클리드 호제법
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

# 1. 일단 통분해서 더한다

n_bunja_1 = bunja_1 * bunmo_2
n_bunmo_1 = bunmo_1 * bunmo_2

n_bunja_2 = bunja_2 * bunmo_1
n_bunmo_2 = bunmo_2 * bunmo_1

sum_bunja = n_bunja_1 + n_bunja_2
sum_bunmo = n_bunmo_1

# 2. 분자와 분모가 서로소가 아닐 경우 기약분수로 나타낸다
GCD = Euclidean(sum_bunja, sum_bunmo)

if GCD != 1:
    sum_bunja = sum_bunja // GCD
    sum_bunmo = sum_bunmo // GCD

print(sum_bunja, sum_bunmo)

근데 아직 내지 말고 일단 보십시오. 이 코드, 로직은 이상 없어서 내도 맞는데 문제가 하나 있다. 두 분수의 분모가 같다면 굳이 통분을 할 필요는 없잖음? 물론 약분은 해야겠지만. 1/4+1/4은 2/4니까 약분하면 1/2이잖아요. 그래서 거기에 대해 if문 하나를 추가할거다.

 

import sys

bunja_1, bunmo_1 = map(int, sys.stdin.readline().split()) # 분수 1호
bunja_2, bunmo_2 = map(int, sys.stdin.readline().split()) # 분수 2호

# 알아두면 좋은 유클리드 호제법
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

# 1. 일단 통분해서 더한다

if bunmo_1 == bunmo_2: # 근데 두 분수의 분모가 같으면 통분 안해도 되잖아요? 
    sum_bunja = bunja_1 + bunja_2
    sum_bunmo = bunmo_1
else: 
    n_bunja_1 = bunja_1 * bunmo_2
    n_bunmo_1 = bunmo_1 * bunmo_2

    n_bunja_2 = bunja_2 * bunmo_1
    n_bunmo_2 = bunmo_2 * bunmo_1

    sum_bunja = n_bunja_1 + n_bunja_2
    sum_bunmo = n_bunmo_1

# 2. 분자와 분모가 서로소가 아닐 경우 기약분수로 나타낸다
GCD = Euclidean(sum_bunja, sum_bunmo)

if GCD != 1:
    sum_bunja = sum_bunja // GCD
    sum_bunmo = sum_bunmo // GCD

print(sum_bunja, sum_bunmo)

그니까 이게 두 분수의 분모가 같으면 통분따원 생략하고 걍 계산하게 한거다. 근데 4줄 추가했을 뿐인데 4밀리초 느려지네… 이거 한줄당 1밀리초인가요?