수 이어가기

 

수 이어가기 

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

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

출력형식

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다. 둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

입력 예

100

 

출력 예

8

100 62 38 24 14 10 4 6

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int now, prev, next, n;
int max_len, max_val, len;

int main() 
{
    int i;

    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        prev = n;
        now = i;
        len = 2;

        while (1)
        {
            next = prev - now;
            if (next < 0)
                break;

            len++;
            prev = now;
            now = next;
        }

        if (len > max_len)
        {
            max_len = len;
            max_val = i;
        }
    }

    printf("%d\n", max_len);
    
    prev = n;
    now = max_val;
    printf("%d %d", prev, now);

    while (1)
    {
        next = prev - now;
        if (next < 0)
            break;

        printf(" %d", next);

        prev = now;
        now = next;
    }

    return 0;
}