[Python] 백준(BOJ) 2635번: 수 이어가기

문제

2635번: 수 이어가기

풀이

규칙에따라 계산하는 함수 calc()를 먼저 만들고, 브루트포스로 입력받은수 N까지 다 돌리며 가장 큰 경우를 찾았다.

N의 반보다 작은 수는 100-> 1->-99 이런식으로 두번밖에 안되기 때문에 시간을 줄이기 위해 N // 2부터 돌렸다.  

import sys

def calc(second_number):
    result = []
    result.append(N)
    result.append(second_number)

    index = 2
    while result[index - 2] - result[index - 1] >= 0:
        result.append(result[index - 2] - result[index - 1])
        index += 1
    return result


max_num = 0
max_sec = 0
N = int(sys.stdin.readline())

for i in range(N // 2, N+1):
    if len(calc(i)) > max_num:
        max_num = len(calc(i))
        max_sec = i

print(max_num)
string = ""
for each in calc(max_sec):
    string += str(each) + " "
print(string)