프로젝트 오일러 033

문제

33번 문제

이상한 방법으로 약분할 수 있는 분수 찾기

사이냅소프트

이상한 약분하기

이번 문제 역시 상당히 쉽습니다. '진부한 경우'를 판단하는 예가 30/50과 같이 분모 · 분자의 1의 자리가 모두 0인 경우만 말하는 것인지 문제에서 명확하게 말해주지는 않습니다만 조금만 생각해보면 이런 경우를 제외하고는 1의 자리가 같은 두 개의 두 자리 자연수가 그 10의 자리 숫자끼리의 비율이 원래 비율과 동일하기는 불가능합니다.

어쨌든 전체 범위는 2개의 두 자리 수를 조합하는 것이고, 분자가 분모보다 크다는 조건이 있기 때문에 검사해야 하는 범위는 크지 않습니다. 검사할 때에는 분모·분자의 1의 자리가 모두 0인 것은 진부한 것으로 보고 제외합니다. 그 외에는 같은 숫자를 제거한 후 분모가 0이 되지 않도록 하는 부분만 신경써주면 답은 쉽게 구해집니다.

from fractions import Fraction
from functools import reduce


def test(x: int, y: int) -> bool:
    o = Fraction(x, y)
    a, b = divmod(x, 10)
    c, d = divmod(y, 10)
    if 0 < b == d:
        return o == Fraction(a, c)
    if b == c and d > 0:
        return o == Fraction(a, d)
    if a == c and b > 0 and d > 0:
        return o == Fraction(b, d)
    if 0 < a and a == d and b > 0 and c > 0:
        return o == Fraction(b, c)
    return False


def main():
    res = [Fraction(x, y) for x in range(10, 99) for y in range(x + 1, 100)
           if test(x, y)]
    print(reduce(lambda x, y: x * y, res).denominator)

main()

Fraction 타입을 사용하면 파이썬의 기본 수치 연산자를 사용할 수 있고, 자동으로 약분하여 기약분수 꼴을 만들어주기 때문에 번잡스러운 다른 구현을 만들지 않아도 됩니다.