C언어 220제] 자기기술 수열(Self-describing Sequence)

출처 : 반크_반크 20년 백서

 

문제]

솔로몬 골롱(Solomon Golomb)의 자기기술 수열<f(1),f(2),f(3),...>은 각 k에 대해 k라는 숫자가 정확하게 f(k)번 등장하는 속성을 가지는 양의 정수로 구성된 유일한 비감소수열이다. 이 수열의 앞부분을 생각해보면 다음과 같은 식이라는 것을 알 수 있다.

어떤 값 n이 주어졌을 때 f(n)의 값을 계산하는 프로그램을 만들어야 한다.

입력
여러 개의 테스트 케이스가 입력될 수 있다. 각 줄마다 하나씩의 정수 n이 입력되며, 정수 한 개가 하나의 테스트 케이스를 이룬다(1<=n<=2,000,000,000). n이 0인 테스트 케이스가 입력되면 입력이 종료되며, 그 케이스는 처리하지 않는다.

출력
각 테스트 케이스에 대해 한 줄에 하나씩 f(n) 값을 출력한다.

입력 예
100
9999
123456
1000000000
0

출력 예
21
356
1684
438744


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제47 자기기술 수열(Self-describing Sequence) p180

 

참고풀이]

#include <stdio.h>

static int sequ[1000000];

int main()
{
   int i, n, cnt, f, Sum;

   while(scanf("%d",&n), n != 0)
   {
      sequ[1]=1;
      sequ[2]=2;
      cnt=3;
      f=2;
      Sum=3;
      for(i=3;i<1000000;i++)
      {
         sequ[i]=f;
         Sum+=f;
         if(Sum>=n) break;
         if(i==cnt)
         {
            f++;
            cnt+=sequ[f];
         }
      }
      if(n==1) i=1;
      else if(n<=3) i=2;

      printf("%d\n",i);
   }
   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 여름