[BOJ] 2635 수 이어가기 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의 중간값까지 순회하며 문제에서 요구하는 대로 반복을 하였다.

마지막에 cnt의 값이 반복이 한번 더 된 채로 나와서 -1을 취해주었다.

 

솔직한 심정으로 이게 왜 맞았는지 잘 모르겠다..

풀이 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

void solve(int n) {
	int cnt = 0;
	int fin[30001] = { 0, };
	for (int i = n; i > n / 2; i--) {
		int temp = 0;
		int j = 2;
		int result[30001] = { 0, };
		result[0] = n;
		result[1] = i;
		int calc = result[j - 2] - result[j - 1];
		//printf("\n------------------------\n");
		do {
			calc = result[j - 2] - result[j - 1];
			result[j] = calc;
			//printf("%d - %d = %d	:	%d\n",  result[j - 2], result[j - 1], calc, j);
			j++;
		} while (calc >= 0);

		if (cnt < j) {
			cnt = j;
			for (int k = 0; k < cnt; k++) {
				fin[k] = result[k];
			}
		}
	}
	cnt = cnt - 1;
	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) {
		printf("%d ", fin[i]);
	}
}
int main(void) {
	int N;
	cin >> N;
	solve(N);
}

결과