[C/C++] 백준 - 2635번 : 수 이어가기

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

2635번: 수 이어가기

문제

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

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

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

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

입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

 

< 구헤야 하는 것 >

규칙에 따라 수를 이어갈 때 만들 수 있는 수들의 최대 개수

 

< 사용해야하는 자료구조 및 알고리즘 판단 >

이 문제는 뭐 자료구조를 사용한다기보다는 그냥 약간의 생각만 필요한 것 같다.

일단 벡터를 사용하긴 했는데 내가 입력한 수가 N이라 할 때 N/2보다 작은 수가 두번째 수로 올 경우 수 이어가기의 길이가 3이상 될 수가 없다. 4번째수가 무조건 0보다 작게 되기 때문

ex) 100 20 80 (-60) : Size -> 3

그래서 N/2부터 입력한 N까지 모두 돌려서 확인해야겠다고 판단했고, 최대 크기도 30000이기 때문에 시간 복잡도도 넉넉해서 바로 구현했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

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

vector<int> v, temp, Answer;
int N, Answer_Size;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	v.push_back(N);
	if (N % 2 == 0) {
		for (int i = N / 2; i <= N; i++) {
			temp = v;
			temp.push_back(i);
			while (1) {
				int isAdd = temp.at(temp.size() - 2) - temp.at(temp.size() - 1);
				if (0 <= isAdd) temp.push_back(isAdd);
				else break;
			}
			if (Answer_Size < temp.size()) {
				Answer_Size = temp.size();
				Answer = temp;
			}
		}
		cout << Answer_Size << endl;
		for (int i = 0; i < Answer.size(); i++) cout << Answer.at(i) << " ";
	}
	else {
		for (int i = (N / 2)+1; i <= N; i++) {
			temp = v;
			temp.push_back(i);
			while (1) {
				int isAdd = temp.at(temp.size() - 2) - temp.at(temp.size() - 1);
				if (0 <= isAdd) temp.push_back(isAdd);
				else break;
			}
			if (Answer_Size < temp.size()) {
				Answer_Size = temp.size();
				Answer = temp;
			}
		}
		cout << Answer_Size << endl;
		for (int i = 0; i < Answer.size(); i++) cout << Answer.at(i) << " ";
	}

	return 0;
}