[백준 2635번] 수 이어가기 (C++)

문제링크 : https://www.acmicpc.net/problem/2635

2635번: 수 이어가기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
vector<int>result;
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=1; i<=N; i++) //음수체크를 위해 N까지
    {
        vector<int>tmp;
        tmp.push_back(N);
        tmp.push_back(i);

        for(int j=1; ; j++)
        {
            if(tmp[j-1]-tmp[j]<0) break;
            tmp.push_back(tmp[j-1]-tmp[j]); //3번째 이후 
        }
        if(tmp.size()>result.size()) result = tmp; //최대 갯수 저장
    }

    cout <<result.size()<<'\n';
    for(auto i : result) cout << i << " ";
    
}

 

처음 입력받은 N과 이후 1~N까지 차례로 1개씩 임시 벡터 tmp에 담아준다.

이때 N까지 담는 이유는 N 이후로는 N-i의 값이 음수이기 때문에 문제의 조건에 맞지 않기 때문이다.

 

이제 3번째 값 부터는 전전값 - 전값을 체크하여 담아주게 된다.

앞서서 담아줬던 N과 i를 이용하여 N-i가 우리가 찾는 값이 되므로 해당 값이 음수가 되는지 체크후 이상없다면 담아준다.

 

최대한 많이 담아야 하므로 tmp 벡터의 사이즈를 체크해 더 커질때마다 result 벡터에 담아 갱신해준다.

이후 사이즈와 내용을 차례로 출력해주면 된다.