[Euler Project 164] 연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수

연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수의 갯수를 구하라. ( http://projecteuler.net/index.php?section=problems&id=164 )

def get_count(n1, n2, remain):  
    #print " "*(20 - remain), n1, n2, remain  
    if cache.has_key((n1, n2, remain)):  
        return cache[(n1, n2, remain)]  
    count = 0  
    sum = n1 + n2  
    if remain == 1:  
        cache[(n1, n2, remain)] = 10 - sum  
        return 10 - sum  
    for n3 in range(10 - sum):  
        count += get_count(n2, n3, remain - 1)  
    cache[(n1, n2, remain)] = count  
    return count  

cnt = 0  
cache = {} # this resolves the time issue.  
for n1 in range(1, 10):  
    for n2 in range(10 - n1):  
        cnt += get_count(n1, n2, 18)  
    #print cnt  
print cnt