수 이어가기 @GODSOL

풀이방법

입력받은 숫자 num에서 가장 많은 수열을 이룰 수 있는 두번째 숫자 temp를 찾는다.

temp가 될 수 있는 최소의 숫자는 num*0.618...이므로, 검사 횟수를 줄이기 위해 num*0.6을 최소한의 범위로 지정한다.

수열의 개수를 세는 방법은 재귀로 구현한다.

#include < iostream > 
using namespace std; 

int check(int n, int t, int cnt) 
{
    if (n < 0) return cnt; 
    cnt++; 
    check(t, n - t, cnt); 
} 

int main() 
{ 
    int num, max = 0, temp = 0; 
    cin >> num; 

    for (int i = num * 0.6; i < num; i++) 
    { 
        int cnt = 0, ck; 
        if ((ck = check(num, i, cnt)) > max) { temp = i; max = ck; } 
    } 
    cout << max << endl; 
    for (int i = num; i >= 0;) 
    { 
        cout << i << " "; 
        temp = i - temp; 
        i = i - temp; 
    } 
}