프로젝트 오일러 033

이상한 약분하기

문제에서 예를 든 ‘진부한 경우’가 조금 모호할 수 있습니다. 30/50과 같이 분모와 분자의 1의 자리가 모두 0인 경우만 말하는 것인지, 다른 ‘진부한’ 경우가 있을지를 좀 생각해봐야 합니다. 각 자리 숫자를 a, b, k로 “ak” / “bk”로 표시하는 경우 실제 수는 (10a + k) / (10b + k)이므로, 이 때 같은 숫자를 지웠을 때 비율이 같아지는 것을 만족하는 k는 0밖에 없습니다. 즉 진부한 경우는 분모와 분자의 끝자리가 모두 0인 경우만 해당합니다.

제외해야할 진부한 경우에 대한 정의만 명확하다면 나머지는 매우 간단합니다.

1. 기약분수 형태로 비교해야 하는 문제가 있지만, Fraction을 사용하면 해결됩니다.
2. 분모 분자에서 같은 숫자는 분모, 분자에서 각각 10의 자리와 1의 자리에 등장할 수 있으므로, 모든 경우를 다 비교해봅니다.
3. 제거하고 남은 숫자가 분모에서는 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:
		# 1의 자리가 같음. 단 0은 안됨
        return o == Fraction(a, c)
    if b == c and d > 0:
		# 분자의 1의 자리와 분모의 10의 자리가 같음
        return o == Fraction(a, d)
    if a == c and b > 0 and d > 0:
		# 분자의 10의 자리와 분모의 10의 자리가 같음
        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()