[ProjectEuler 206] 1_2_3_4_5_6_7_8_9_0 = n*n 인 유일한 n구하기.

#!/usr/bin/env python

'''
for x in xrange(101010101, 138902663):
    if xx % 10 != 7 or xx % 10 != 3:
        continue
    xx = 10*x
    s = str(xx*xx)
#   print s
#   print "1_2_3_4_5_6_7_8_9_0"
    MeetCondition=True
    for i in xrange(1, 10):
        if s[2*(i-1)] != str(i):
            MeetCondition=False
            break
    if MeetCondition:
        print xx*xx, xx
        print "1_2_3_4_5_6_7_8_9_0"
'''
s = "1_2_3_4_5_6_7_8_9_0"
def GetList(lst, length):
    if length == 9:
        new_lst = []
        for n in lst:
            m = 1*(10**length) + n
            sqr_str = str(m*m)
            MeetCondition = True
            for i in xrange(19):
                if i%2 == 1:
                    continue
                if sqr_str[i] != s[i]:
                    MeetCondition = False
                    break
            if MeetCondition:
                print "# %19d"%(m*m)
                #print "# %s"%sqr_str
                print "# %s"%s
                new_lst.append(m)
        return new_lst
    else:
        new_lst = []
        for n in lst:
            for d in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
                m = d*(10**length) + n
#               print s
                sqr_str = str(m*m)
                sqr_str = "00" + sqr_str
                MeetCondition = True
                for i in xrange(length+1):
                    if i %2 == 1:
                        continue
                    if sqr_str[-(i+1)] != s[-(i+1)]:
                        '''
                        print "%19s"%sqr_str
                        print "%19d"%(m*m)
                        print s
                        print i, sqr_str[-(i+1)], s[-(i+1)]
                        '''
                        MeetCondition= False
                        break
                if MeetCondition:
                    print "# %19d"%(m*m)
                    #print "# %s"%sqr_str
                    print "# %s"%s
                    new_lst.append(m)
        return GetList(new_lst, length+1)
print GetList([0], 1)

위에 커멘트아웃 해 놓은 코드는 무식쟁이(brute-force)방법. 실제로 문제를 1분 안에 풀어낸 것은 리스트를 반환하는 재귀함수. n의 최하위 k자리가 정해지면, n*n 의 최하위 k자리도 그 상위 자리수에 상관없다는 성질을 이용했다.