백준 문제풀이 - 2635 번

링크 -> https://www.acmicpc.net/problem/2635

1. 요약 및 풀이방법

첫 번째 수가 주어지면, 주어진 규칙에 따라 이어지는 다음 수를 구한다.
이때 주어진 규칙으로 만들어지는 최대 개수의 수들을 구하는 문제이다.

주어진 규칙은 다음과 같다.

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

ex)

• 입력

100

• 출력

8
100 62 38 24 14 10 4 6

다음과 같이 풀이했다.
재귀를 이용해 규칙을 따르는 tmp 벡터를 만든다.
tmp 벡터가 answer벡터보다 size가 크면,
answer벡터는 tmp벡터로 업데이트 된다.

2. Code

#include <iostream>
#include <vector>

std::vector<int> g_answer;
std::vector<int> tmp;

void solution(int first, int second)
{
    if (first < second)
        return ;
    tmp.push_back(first - second);
    solution(second, first - second);
}

void print()
{
    std::cout << g_answer.size() << std::endl;
    for (int i = 0; i < g_answer.size(); i++)
        std::cout << g_answer[i] << ' ';
    std::cout << std::endl;
}

int main()
{
    int f_num;

    std::cin >> f_num;
    for (int i = 1; i <= f_num; i++)
    {
        tmp.push_back(f_num);
        tmp.push_back(i);
        solution(f_num, i);
        if (tmp.size() > g_answer.size())
            g_answer = tmp;
        tmp.clear();
    }
    print();
    return (0);
}

3. 학습 내용

익숙하지 않은 재귀함수를 연습해보는 문제였다.
추가로 g_answer벡터를 새로 업데이트하는 g_answer = tmp; 코드가
최선의 방법인지 알아봐야겠다.

4. 결과