BOJ 2635 수 이어가기
문제
다음과 같은 규칙에 따라 수들을 만들려고 한다.
첫 번째 수로 양의 정수가 주어진다.
두 번째 수는 양의 정수 중에서 하나를 선택한다.
세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.
첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.
입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.
입력
첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.
출력
첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.
둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.
문제 풀이
N = int(input()) #100
max_list = []
max_cnt = 0
for i in range(N, -1, -1):
cnt = 0
list_a = [N, i]
while True:
temp = list_a[cnt] - list_a[cnt + 1]
if temp < 0:
break
else :
list_a.append(temp)
cnt += 1
if max_cnt <= cnt :
max_cnt = cnt
max_list = list_a
str_s = ''
for i in max_list:
str_s += (str(i) + " ")
print(len(max_list)) # 8
print(str_s) #100 62 38 24 14 10 4 6처음 입력받은 input 값만큼 뒤에서부터 하나씩 계산하는 브루트 포스 방법으로 문제를 풀었다. while문으로 n-2번째 값에서 n-1번째 값을 뺀 결과가 0보다 클때까지 반복하면서 해당 값들을 list_a에 저장하였다. while문을 돌 때마다 count를 세어주어 count가 제일 클 때의 list를 max_list로 저장하여 문제를 해결하였다.
처음에는 for문의 range에 입력받은 N값은 포함되지 않는다고 생각하여 for i in range(N-1, -1, -1)로 놓고 문제를 풀었지만 계속 100%에서 틀렸다고 나왔고 더 보니 자기 자신 N을 포함시키지 않아 문제가 해결되지 않았던 것이다. 범위에 자신이 포함되는지 안되는지를 잘 생각해야 될 것이다.
