[python] 백준 2635 수 이어가기

https://www.acmicpc.net/problem/2635

2635번: 수 이어가기

 

문제 해결

• 첫 번째 수가 주어지고 두 번째수는 첫번째 수 이하인 부분들을 반복해나가면서 최적의 수를 찾아야한다.
• 사실 재귀를 사용해서 최대 길이를 찾는 것은 어렵지 않다.
• 하지만 문제를 잘 읽어야하는게 이후 나오는 수들은 0이여도 상관이 없다는 것이다.(음이 아닌 수이기 때문)
• 문제 난이도는 쉬운 편

 

CODE

import sys
input = sys.stdin.readline


def dfs(A:list):
    global target, ans
    if A[-2] - A[-1] >= 0:
        A.append(A[-2] - A[-1])
        dfs(A)
    else:
        if ans < len(A):
            target = A
            ans = len(A)
def main():
    global ans, target
    for i in range(1,n+1,1):
       A = [n, i]
       dfs(A)
    print(ans)
    print(*target)
if __name__ == "__main__":
    n = int(input())
    ans = 0
    target = []
    main()