[PE] Project Euler 57

프로젝트 오일러 57번은 패턴만 찾으면 거저먹는 문제. i번째 분수가 b/a꼴로 생겼다고 하면, i+1번째 분수는 1+1/(1+b/a) = 1+1/((a+b)/a) = 1+a/(a+b) = (2a+b)/(a+b)가 되어, i번째 분수의 분자, 분모로 i+1번째 분수의 분자, 분모를 바로 구할 수 있으니 이를 활용하자.

sol=0
a,b=1,1
for _ in range(1000):
    a,b=a+b,2*a+b
    if len(str(a))<len(str(b)): sol+=1
print(sol)

새로 만든 분자, 분모를 string으로 바꾸어 길이를 찾아 비교하면 끝나는 간단한 문제다. 시작을 1/1로 하면 첫 분수인 3/2를 얻을 수 있으므로 for문도 깔끔하게 1000번만 돌면 된다.