C언어 217제] 1의 개수(Ones)

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

 

문제]

2나 5로 나눌 수 없는 0 이상 10,000 이하의 정수 n이 주어졌는데, n의 배수 중에는 10진수로 표기했을 때 모든 자리 숫자가 1인 것이 있다. 그러한 n의 배수 중에서 가장 작은 것은 몇 자리 수일까?

입력
한 줄에 하나씩의 정수가 들어있는 파일

출력
입력된 정수 a에 대해 p=aXb(b는 0보다 큰 정수)라고 할 때 p=∑1X10^i를 만족시키는 가장 작은 정수 x(x>0)를 한 줄에 하나씩 출력한다.

입력 예
3
7
9901

출력 예
3
6
12


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제 36 1의 개수(Ones) p156

 

참고풀이]

#include <stdio.h>

int main()
{
   int n, x, t, Sum;

   while(scanf("%d",&n)==1)
   {
      Sum=0;
      x=0;
      t=1;
      while(1)
      {
         Sum=(Sum+t)%n;
         x++;
         t=(t*10)%n;
         if(Sum==0) break;
      }
      printf("%d\n",x);
   }

   return 0;
}

 

참고풀이 결과]

결과나오는 과정의 횟수)

 

실제결과)

 

 

 

 

 

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