[BOJ/C++] 수 이어가기(2635번)

1. 개요

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

2635번: 수 이어가기

1-1. 설명

다음과 같은 규칙에 따라 수를 만든다

 - 첫 번째 수로 양의 정수가 주어짐

 - 두번째 수는 임의로 양의 정수중 하나 선택

 - 세번째 수부터는 앞의 앞의 수에서 앞의 수를 빼서 생성

 - 음의 정수가 만들어지면, 이 음의 정수는 버리고 더 이상 수를 만들지 않음

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

1-2. 제한 사항

 - 첫 줄에 첫 번째 수가 주어지며 이 수는 30,000 이하 양의 정수

---

2. 구현

2-1. 풀이

브루트포스 방식을 사용하였다. 첫번째 수에서부터 0에서 수까지 반복문을 활용하여 규칙에 따라 숫자를 생성한 후, count를 세어 각각 비교해주고 큰 숫자를 마지막에 출력해주었다. 

2-2. 코드

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

vector<int> resNum;
vector<int> compareNum;
int N, result = 2, curCount = 0;

void solution(int preNum, int num, int count);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = N; i >= 0; i--) {
        compareNum.clear();
        compareNum.push_back(N);
        compareNum.push_back(i);

        solution(N, i, 2);
        if (result < curCount) {
            result = curCount;
            resNum = compareNum;
        }
    }

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

    return 0;
}

void solution(int preNum, int num, int count) {
    int curNum = preNum - num;
    if (curNum >= 0) {
        compareNum.push_back(curNum);
        solution(num, curNum, count + 1);
    }
    else curCount = count;
}