2635 수 이어가기

이걸 왜 어렵다고 생각했을까??? 뭔가 터질 것 같아서 고민만 하다가 오늘 그냥 만들어 봤는데 통과했다. 최대 30000이 주어지고 한 번 확인할 때마다 30000번 확인 한다고 하면 900000000번.. 9억이긴 한데 30000번 돌지 않아서 통과한 것 같다. 애매하고 찜찜해

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


void calc(int one, int two, vector<int> &v)
{
    if (one < 0)
        return;
    
    v.push_back(one);
    calc(two, one-two, v);
}

int main() {
    int n;
    scanf("%d", &n);
    
    vector<int> maxv;
    for (int i = 1; i <= n; i++)
    {
        vector<int> v;
        calc(n, i, v);
        
        if (v.size() > maxv.size())
            maxv = v;
    }
    
    printf("%d\n", maxv.size());
    for (int i = 0; i < maxv.size(); i++)
        printf("%d ", maxv[i]);
    
    return 0;
}