[백준 2635번] 수 이어가기

[백준 2635번] 수 이어가기

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 보다 같거나 작은 양의 정수이다.

 

 출력

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

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

 

 

 풀이

#include <iostream>
using namespace std;
int N;
int ff(int a, bool f){
	int k = N;
	int i=0;
	while(k >= 0){
		int temp = k;
		if(f) cout << temp <<' ';
		k = a;
		a = temp - a;
		i++;
	}
	return i;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	
	int target = -1;
	int tnum = 0;
	for(int i=N/2; i<=N;i++){
		int a = ff(i, false);
		if(target < a){
			target = a;
			tnum = i;
		}
	}
	
	cout << target << '\n';
	ff(tnum, true);
	return 0;
}

 N보다 작고 N/2보다 같거나 큰 자연수들을 대상으로 완전 탐색하면 되는 문제이다. 규칙으로 만들어지는 수들의 최대 개수에 해당하는 i를 저장해뒀다가 마지막에 해당 숫자로 출력해주면 된다. k>=0, i<=N에서 등호를 안넣었다가 한번 틀렸다. 1이 반례였는데 1의 경우 1 1 0 1 로 4가 정답이다.