[M2S] 2009년 01월 30일 금요일 C언어 DailyQuiz 12 ( 1의 횟수 )

1의 횟수

양수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다.

예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다.

ex) 13  >  1, 10, 11, 12, 13

두번째 양수는 무엇인가?

출처 : http://kaisyu.blogspot.com/2007/02/google_14.html


날짜를 보니 작년 문제인듯 싶다. 1의 횟수
1에서 부터 n까지 모든 숫자를 각 자릿수 숫자를 한자리 숫자들의 리스트로 나누어서 1의 갯수를 구한뒤 이를 모두 합치면 간단히 풀 수 있다.

간단히 풀수 있는 문제 이지만 풀다보니 n의 복잡도가 아닌 상수 복잡도로 0에서 양의 정수 n까지의 1의 갯수를 발견할 수 있음을 깨달았다.

알고리즘을 간단히 설명하자면 각 자릿수의 수만 고려해 본다면 자연수 의 특성상 일정한 규칙으로 정렬 되는데 예를 들어 일의 자리의 수만 나열해 보면 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 ...
이런식으로 나열된다. 잘보면 1이 10의 주기로 나오는 것을 알 수 있다.

십의 자리도 마찬가지로 0 0 0... 0 1 1 1 .. 1 이런식으로 한 숫자당 10 번 씩 반복하며 0 ~ 9 로 반복됨을 알 수 있다. 이 규칙은 백의 자리 이상에서도 성립한다. 단지 각 숫자의 반복이 자릿수가 늘어날수록 1 , 10 , 100 등 10의 배수로 늘어날 뿐이다.

이러한 규칙을 이용하면 1에서 부터 모두 구하지 않더라도 1의 갯수를 개산할 수 있는데
아래는 이를 얼랭으로 풀이한 결과이다.

f(Val) -> f(Val,10).

f(Val, 10) ->
    Value = Val + 1,              % 0 ~ N 까지의 갯수는 N+1 이다
    Rem = Value rem 10,      % 10으로 나눈 나머지
    G = (Value - Rem) / 10,  % 주기를 구한다.
    Last = case Rem of        % 주기를 채우지 못한 나머지에서의 1의 갯수를 구함 
        N when N < 2 -> 0;
        _ -> 1
    end,
    G + Last + f(Value,100);   % 다음 자리수의 1의 갯수와 합한다.

f(Val, Base) when Val*10-1 < Base -> 0;   % 모든 자릿수에 대해 고려완료

f(Value,Base) ->
    Rem = Value rem Base,
    G = (Value - Rem) / Base,         % 주기를 구한다.
    Last = case Rem / Base * 10 of % 주기를 채우지 못한 나머지에서의 1의 갯수를 구함 
        N when N < 1 -> 0;
        N when N < 2 -> (Rem - (Base / 10));
        _ -> Base / 10
    end,
    G * Base / 10 + Last + f(Value,Base*10).
                                                            % 자릿수/10 만큼 반복되며 주기가 돌아가므로
                                                            % 주기에 자릿수/10을 곱한다.

ps. Max 값은 1,000,000 으로 잡는다.
      N까지의 1의 숫자를 매번 헤아리는게 아닌 N까지의 숫자를 이용해서 1이 몇회 나오는데
    자릿수만큼의 루프를 통해서 찾아내는 방법으로 연산 횟수를 크게 줄이는 게 광건이다.

count_One.exe

기한 : 2009년 2월 2일 월요일 PM 02:00 까지.

제출 : rockdrumy@nate.com or 네이트온.

제출방법 : 워드문서로 레포트 형식과 동일하게 소스와 실행화면 스샷과 함께 작성하고, 
               Word 파일과 c 파일 1개로 압축하여 제출. 

궁금한 점은 무조건 저한테만 문의 바람. 웹사이트 & 네이버 지식검색 참조 금물.