[C++/백준] 수 이어가기

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

문제 설명

다음과 같은 규칙에 따라 수들을 만들려고 한다.

첫 번째 수로 양의 정수가 주어진다.
두 번째 수는 양의 정수 중에서 하나를 선택한다.
세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

 

풀이

주어지는 첫번째 수가 30,000보다 같거나 작은 양의 정수이므로 두번째 수를 1~첫번째 수로 반복문을 돌리며 직접 수열을 구한다.

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

int n, cur, pre;
vector<int>ans;

int main() {

	cin >> n;
	for (int i = 1; i <= n; i++) {
		pre = n;
		cur = i;
		vector<int>tmp;
		tmp.push_back(pre);
		tmp.push_back(cur);

		while (true) {
			int nxt = pre - cur;
			if (nxt < 0) break;
			tmp.push_back(nxt);
			pre = cur;
			cur = nxt;
		}

		if (tmp.size() > ans.size()) ans = tmp;
	}

	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}
}