[C언어 기출문제&풀이] 수 이어가기

프로그램 명: numtonum

제한시간: 1 초

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

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

첫 번째 수로 100 이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수를 만들면 7 개의 수들 100,60,40,20,20,0,20 이 만들어진다.

그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8 개의 수들 100,62,38,24,14,10,4,6 이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라 만들어지는 수들의 개수가 다를 수 있다.

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

입력 형식

입력 파일에 첫 번째 수가 주어진다. 이 수는 30000 보다 같거나 작은 양의 정수이다.

출력 형식

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

입출력 예

입력

100

출력 

8
100 62 38 24 14 10 4 6

보충 설명

4 가 입력으로 주어지는 경우

• 두 번째 수가 1 인 경우 : 4 1 3
• 두 번째 수가 2 인 경우 : 4 2 2 0 2
• 두 번째 수가 3 인 경우 : 4 3 1 2
• 두 번째 수가 4 인 경우 : 4 4 0 4

두 번째 수가 2 인 경우가 최대 길이 5 이므로 출력은

5
4 2 2 0 2

출처:koi 기출

소스코드 

#include <stdio.h>

int main()

{

 int i,j,fst,head,real,temp,max=0,maxn,cnt=0;

 scanf("%d",&fst);

 for(i=1;i<=fst;i++)

 {

  head=fst;

  real=i;

  cnt=0;

  printf("%d %d ",head,real);

  for(;head-real>=0;)

  {

   temp=real;

   real=head-real;

   head=temp;

   printf("%d ",real);

   cnt++;

  }

  if(max<cnt+2) 

  {

   max=cnt+2;

   maxn=i;

  }

  printf("%d\n",max);

 }

 printf("%d\n",max); 

 printf("%d %d ",fst,maxn);

 head=fst;

 real=maxn;

 for(;head-real>=0;)

 {

  temp=real;

  real=head-real;

  head=temp;

  printf("%d ",real);

 }

}