[백준 알고리즘 #2635] 수 이어가기(Python3)

문제 링크: www.acmicpc.net/problem/2635

2635번: 수 이어가기

---

---

정답 코드

A = int(input())
result = []
max = 0

for i in range(A+1):
    tmp = [A]
    tmp.append(i)
    
    while (tmp[-2] - tmp[-1]) >= 0:
        tmp.append(tmp[-2] - tmp[-1])
        
        if len(tmp) > max:
            max = len(tmp)
            result = tmp

print(len(result))

for i in result:
    print(i, end=" ")

 

문제 풀이

두 번째 수는 정해지지 않았으며 모든 경우의 수를 다 검사하는 브루트포스 알고리즘이다. 따라서 0부터 A까지 모든 수를 다 넣어보면서 최대 길이를 비교한다.

 

결국 배열 내부의 새로운 수를 만들어내기 위해서 배열의 끝부분 부터 접근하는 방법을 택했다.

그리고 while의 조건을 0이상의 수로 설정함으로써 음수가 나오는 경우에 반복을 종료한다.

 

그렇게 완성된 list의 길이를 비교해서 이전까지의 리스트의 최대길이를 저장하는 max와 비교한 후 max 값을 변경한.

 

마지막으로, 처음 작성한 코드의 경우 예제 입력인 100을 입력하였을 때, 예제 출력과 동일하게 나왔다.

 

8

100 62 38 24 14 10 4 6

 

만약 결과는 동일하게 나오지만 정답을 인정해 주지 않는 경우, 1을 입력한 경우 예제 출력은

 

4

1 1 0 1

 

와 같이 나오니 이 부분도 추가로 실행시켜 보는 것을 추천한다.