백준 2635. 수 이어가기

https://www.acmicpc.net/problem/2635

2635번: 수 이어가기

 

첫 번째로 주어지는 수가 30000보다 같거나 작은 양의 정수이기 때문에 브루트포스로 충분히 풀수 있다.

 

1. 두번째 수를 1부터 n까지 바꿔보면서 수들을 만든다.

2. 만들어진 수의 길이가 현재까지 중 가장 길다면 다른 벡터 ans 에 저장해놓는다.

3. 1부터 n까지 다 넣어본 후 , ans 벡터의 크기와 내용물을 출력한다.

 

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> v;

int longest = 0;
vector<int> ans;

void IsItLongest()
{
    // 현재 벡터의 크기가 longest보다 크다면 갱신
    if(v.size() > longest)
    {
        ans.clear();

        for(int x : v)
            ans.push_back(x);

        longest = ans.size();
    }

    v.clear();
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        // 첫번째 수
        int num = n;
        v.push_back(num);
        // 두번째 수
        num = i;
        v.push_back(i);

        int idx = 2;
        while(num >= 0)
        {
            num = v[idx-2] - v[idx-1];
            v.push_back(num);
            idx++;
        }

        v.pop_back(); // 마지막 음수 제거

        IsItLongest();
    }


    cout << ans.size() << '\n';
    for(auto x : ans)
        cout << x << ' ';

}