백준2635 - 수 이어가기

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

2635번: 수 이어가기

문제 풀 때는 몰랐는데 수열이 x와 k의 계수가 피보나치 꼴로 나온다. x는 0부터 시작한다고 가정을 하고 짝수번째 수열이면 -가 붙고 홀수번째 수열이면 +가 붙는다. k는 x와 반대로 부호가 붙는다. 우선 수가 30000까지로 작기 때문에 임의로 50개의 계수를 구한 뒤 반복문을 돌렸다.

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
	//문제는 ax + bk >= 0을 만족하는 x를 찾고 그 x중에서 최고로 많은 수열을 나타낼 수 있는 수를 찾아서 수열을 적는것.
	int k; //주어진 k이하의 수를 찾기 위하여 설정한 k 
	int big = -1; //가장 많은 수열 인자가 있을 때의 수열의 총 인자 갯수
	int cnt = 0; //현재 몇 번째 수열 인자가 생겼는지 구하는 변수
	vector<int> a; //x의 계수
	vector<int> b; //k의 계수
	vector<int> temp; //반복문의 과정을 임시로 담는 변수
	vector<int> ans; //현재 수가 최대의 수열인자를 가질 때 그 기록을 담는 변수 

	cin >> k;

	//x의 계수를 구하기, 초항으로 0, 둘째항으로 1을 넣는다. 그 다음 짝수 번째이면 음수, 홀수 번째이면 양수로 선언한다.
	a.push_back(0); 
	a.push_back(1);
	for (int i = 2; i < 50; i++) {
		if (i % 2 == 0) {
			a.push_back(-(abs(a[i - 2]) + abs(a[i - 1])));
		}
		else {
			a.push_back((abs(a[i - 2]) + abs(a[i - 1])));
		}
	}

	//k의 계수를 구하기, 초항으로 1, 둘째항으로 0을 넣는다. 그 다음 짝수 번째이면 양수, 홀수 번째이면 음수로 선언한다.
	b.push_back(1);
	b.push_back(0);
	for (int i = 2; i < 50; i++) {
		if (i % 2 == 0) {
			b.push_back((abs(b[i - 2]) + abs(b[i - 1])));
		}
		else {
			b.push_back(-(abs(b[i - 2]) + abs(b[i - 1])));
		}
	}

	//최대의 경우의 수를 찾는 과정, 관계식의 의거하여 풀었다.
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j < a.size(); j++) {
			if (a[j] * i + b[j] * k < 0) {
				break;
			}
			temp.push_back(a[j] * i + b[j] * k);
			cnt++;
		}
		if (big < cnt) {
			big = cnt;
			ans = temp;
		}
		cnt = 0;
		temp.clear();
	}

	//결과 출력
	cout << big << '\n';
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}
}