Project Euler #34 - digit factorials

프로젝트 오일러 34번
145 = 1! + 4! + 5! 이다. 이런 성질을 만족하는 숫자를 모두 찾아서 더하면? 단 1!=1, 2!=2는 뻔한 경우로, 제외한다.

9! 이 약 36만 정도니까, 최대 7자리 숫자까지 가능하다. 그런데 9999999 != 9! * 7 이고.. 종이에 조금 끄적거려 보면 7자리가 되는 경우는 없다.

1자리~6자리의 모든 수에 대해서 위의 조건을 만족하는지 보려면 대략 천만번 loop를 돌아야 한다. 반대로 [1,1,2,6,24,...] 숫자들을 6개까지 더해서 위의 조건을 만족하는지 보는 게 더 효율적이다. 4000개 정도의 숫자만 체크하면 된다.

f = [0,1]
for i in range(1,10):
    f.append(f[-1]*i)

a = {x1+x2+x3+x4+x5+x6 for x1 in f for x2 in f for x3 in f for x4 in f for x5 in f for x6 in f if x1<=x2<=x3<=x4<=x5<=x6}

sm = 0
for n in [n for n in a if n >2]:
    if n == sum([f[int(x)+1] for x in str(n)]): sm += n

print sm

예쁘지는 않지만.. f[x+1]에는 x! 에 해당하는 값이 들어가 있도록 했다.
a에는 최대 6자리 모든 조합이 들어가도록 했다. if 뒤에 "and x1+x2+...+x6 > 2"를 추가하고 싶지만 한 줄이 너무 길어져서... --;
이렇게 하면 0.2초 걸린다. 위에서 "종이에 조금 끄적거려 보면"을 생략하고 7자리까지 조건을 체크하면 더 오래 걸린다.

시간을 더 줄이는 방법! 아래의 코드를 실행하면 7자리까지 모두 체크하면서 시간은 0.03초로 줄어든다. 위의 a = ... 에 해당하는 코드를 길게 풀어 쓴 건데, 보기에는 지저분해도 효과는 좋다. 31번 동전 조합 문제도 이렇게 풀면 실행 시간이 훨씬 줄어든다.

f = [1]
for i in range(1,10):
    f.append(f[-1]*i)

rs = set()
for n9 in range(7):
    s9 = f[9] * n9
    ub8 = 7 - n9
    for n8 in range(ub8):
        s8 = s9 + f[8] * n8
        ub7 = ub8 - n8
        for n7 in range(ub7):
            s7 = s8 + f[7] * n7
            ub6 = ub7 - n7
            for n6 in range(ub6):
                s6 = s7 + f[6] * n6
                ub5 = ub6 - n6
                for n5 in range(ub5):
                    s5 = s6 + f[5] * n5
                    ub4 = ub5 - n5
                    for n4 in range(ub4):
                        s4 = s5 + f[4] * n4
                        ub3 = ub4 - n4
                        for n3 in range(ub3):
                            s3 = s4 + f[3] * n3
                            ub2 = ub3 - n3
                            for n2 in range(ub2):
                                s2 = s3 + f[2] * n2
                                ub1 = ub2 - n2
                                for n1 in range(ub1):
                                    s1 = s2 + f[1] * n1
                                    if s1 > 2 and s1 == sum([f[int(x)] for x in str(s1)]):
                                        rs.add(s1)

print sum(rs)

참고로.. 9!*7까지의 모든 자연수에 대해 위의 조건을 만족하는지 체크해 보면 15초 정도 걸린다. 좋지 않은 방법

f = [1]
for i in range(1,10):
    f.append(f[-1]*i)

sm = 0

for n in range(10,7*f[9]):
    if n == sum([f[int(x)] for x in str(n)]): sm += n

print sm