[백준/Python] 2635번 - 수 이어가기

 

문제

https://www.acmicpc.net/problem/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 보다 같거나 작은 양의 정수이다.  

 

 

출력

 

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

 

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

 

 

풀이

 

이 문제는 두개의 방법으로 풀 수 있다.

​

[풀이1]

 

기본적으로 이 문제는 첫번째 수의 범위가 30000이기 때문에 브루트 포스로 풀 수 있다.

어떤 수 N이 주어졌을때 0부터 N까지 수들을 두번째 수로 정해서 수열의 길이를 구한다.

그래서 0 부터 N까지 수를 두번째 수로 정하고 수열을 구한 뒤 수열의 최대 길이였던 숫자 m을 구하도록 풀었다.

​

[풀이2]

 

문제를 브루트 포스로 풀기 전에 첫 번째 수에 일정 비율을 곱하면 바로 두번 째 수의 값을 알 수 있을 것이라는 생각이 들었다.

 

하지만 비율이 얼마가 될지 바로 떠오르지 않았는데, 점화식을 세워보니 금방 알 수 있었다.

첫 번째 수를 a1이라고 하고 두번째 수를 a2라고 가정하자 그러면

​

$$a_3 = a_1 - a_2$$

$$a_4=a_2-a_3 이므로$$

$$a_4=2a_2 - a_1$$

$$a_5=2a_1-3a_2$$

​

위와 같이 나타나는 모습을 볼 수 있다.

자세히 보면 앞 뒤 수를 빼가면서 구하는 방식이기 때문에 a1 과 a2 의 계수가 피보나치 수열의 모습을 보이는 사실을 파악할 수 있다.

 

그러므로 우리가 원하는 가장 긴 길이의 수열을 찾기 위해서는 앞 숫자와 뒤 숫자를 뺄 수 있는 상황이 가장 많아야 하므로

$$a_n=xa_1-ya_2>=0$$

을 최대한 만족하면 된다.

 

그러므로 x가 1일 때 y의 비율은 피보나치 수열의 비율 즉, 황금비 임을 알 수 있다.

 

 

 

Code (브루트 포스)

 

 

N=int(input())
max_n=0
ans=0
for i in range(N+1):
    n1=i
    n0=N
    num=1
    while n1>=0:
        n0,n1=n1,n0-n1
        num+=1
    if max_n<num:
        ans=i
        max_n=num
n0=N
print(max_n)
while n0>=0:
    print(n0,end=' ')
    n0,ans=ans,n0-ans

 

 

 

Code (피보나치 수열)

 

 

n=int(input())
a=n*61040//98765+1 # 첫번째 수가 98765 일 때 피보나치 수열의 비율로 두번째 수를 구한 것
# a=int(n*0.61803)+1, a=n*18541//30000+1 로 해도 된다...
d=[]
while n>=0:
    d.append(n)
    n,a=a,n-a
print(len(d))
print(*d)

 

 

---

 

예전에 풀었던 문제인데 내가 푼 코드를 보고 바로 이해가 안돼서 다시 생각해봤다...

 

30000보다 큰 숫자 98765를 대충 넣어두면 어떻게 코드만 보고 바로 이해가 되겠냐고;;; 에효

​

 

 

 

 

2635번: 수 이어가기