[BOJ/백준] 2635 - 수 이어가기 (2635 )

문제

문제링크

입력으로 첫번째 수가 주어질 때 아래 규칙으로 만들어지는 최대 개수의 수들을 구하라.

• 첫 번째 수로 양의 정수가 주어진다.
• 두 번째 수는 양의 정수 중에서 하나를 선택한다.
• 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다.
• 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

 

풀이

후보리스트에는 입력 수와 1부터 n까지의 수 중 랜덤으로 넣는다. 모든 수를 다 고려해야 하므로 for문으로 모든 케이스를 다 살필 것이다.

후보 리스트에 while문으로 위 규칙을 따라 수를 생성해 저장한다.

만약 final 리스트보다 후보리스트의 길이가 더 길다면 final 리스트를 이번 시도의 후보리스트로 교체한다.

두번째 수가 n인 시도까지 모두 끝났다면 이제 final 리스트에는 규칙을 따르는 최대 개수의 배열이 저장되어있다.

이제 그 길이와 모든 요소를 출력하면 된다.

 

코드

n=int(input())

final=[]
for i in range(1, n+1):
  cand = [n, i]
  while len(cand)>=2 and (cand[-2]-cand[-1])>=0:
    cand.append(cand[-2]-cand[-1])
  if len(final)<=len(cand): final=cand
print(len(final))
print(*final)