[BOJ] 2635번 수 이어가기 - 파이썬

📒 문제

다음과 같은 규칙에 따라 수들을 만들려고 한다.

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

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

✏️ 풀이

처음에는 두번째 수를 정할 때, 어차피 첫번째 수와 두번째 수의 차이를 통해 세번째 수를 정하게 되기 때문에 첫번째 수의 절반보다 큰 값이 나와야 계산이 조기종료(?)되는 일이 없을 것이라 생각하고 다음과 같이 코드를 구성했다.

first_num = int(input())
second_num = first_num // 2 + 1  # 절반 이하로 2번째 수를 정하게 되면 4번째 수에서 끝나기 때문
len_result = 0
result = []

for i in range(first_num-1, second_num, -1):
    result_list = [first_num, i]
    j = 0
    while True:
        last_num = result_list[j] - result_list[j+1]
        j += 1
        if last_num < 0:
            break
        result_list.append(last_num)
        if len_result < len(result_list):
            len_result = len(result_list)
            result = result_list[:]

print(len_result)
final_result = [str(result[i]) for i in range(len(result))]
print(' '.join(final_result))

하지만 이 방법이 틀렸는지, 백준에서 100%까지 채점이 되다가 마지막에 틀렸습니다!가 떴다..

조금이라도 빠르게 할 수 있는 방법을 찾고자해서 해본 방법인데, 이 방법이 틀렸다는 것을 알게 되어 정석적으로 0부터 일일이 해보았다.
입력값이 30000까지 이므로 하나하나해주어도 시간제한에는 영향이 없었기 때문이다.

first_num = int(input())
# second_num = first_num // 2 + 1  
# # 절반 이하로 2번째 수를 정하게 되면 4번째 수에서 끝나기 때문 -> 틀린 아이디어 같음.
len_result = 0
result = []

# for i in range(first_num-1, second_num, -1):
for i in range(first_num+1):
    result_list = [first_num, i]
    j = 0
    while True:
        last_num = result_list[j] - result_list[j+1]
        j += 1
        if last_num < 0:
            break
        result_list.append(last_num)
        if len_result < len(result_list):
            len_result = len(result_list)
            result = result_list[:]

print(len_result)
final_result = [str(result[i]) for i in range(len(result))]
print(' '.join(final_result))

이 방법을 이용한 결과 정답을 얻을 수 있었다.
메모리는 29200kb, 시간은 108ms로 적당한 결과를 얻을 수 있었다.