GLAT...

양수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다. 두번째 양수는 무엇인가.

수학 참고서에나 나올 법한 얘기지만 이 문제는 구글의 입사 지원자들이 통과해야 할 구글 연구소 능력 시험(GLAT) 중 하나다. '최고 괴짜'를 찾아내겠다는 목표로 시작된 프로그램으로 길거리 광고판 등에 문제를 내놓고 이 문제를 푼 사람은 이력서와 함께 정답을 구글로 보내면 된다.

출처: http://news.media.daum.net/economic/finance/200609/17/mk/v14060984.html

다음에 난 기사를 보다가 살짜쿵 호기심이 생겼다. 구글이라는데 또 발끈해서 문제를 풀어볼라고 낑낑대다가 안돼는 것이었다. 점화식 어쩌고 저쩌고 식 세우다가 나의 초라한 수학적 한계를 실감하고는 컴퓨터에게 물었다. 컴퓨터는 199981이라고 나에게 알려줬으나 정답인지 확인할 길은 없다. 그거 다 헤아리고 있을 수도 없공 ㅋㅋ- 구글에 들어가려면 역시 똑똑해야 하긴 하나 보다. ㅎㅎ- 수학 잘하는 사람이 부러울 때는 정말 이럴때 말고는 ㅎㅎ-~ ^^

아래는 풀어본 소스 코드다. 그냥 재귀로 만드니 스택 오버플로 나는거 같아서 캐쉬를 쓰도록 고쳤다가 생각해보니 그럴 필요도 없을것 같았다. 그래서 변수 하나로 대체한것이 두번째 루프다.

#include <stdio.h>   
#include <map>   
  
using namespace std;   
map<int, int> g\_Cache;   
  
int gf(int n)   
{     
    int k, r = 0;     
  
    do     
    {          
        k = n % 10;          
        if(k == 1)              
            ++r;     
    } while ((n /= 10) > 0);     
  
    return r;   
}   
  
int f(int n)   
{     
    map<int,int>::iterator it = g\_Cache.find(n);     
  
    if(it != g\_Cache.end())          
        return it->second;     
  
    int result;     
    if(n <= 1)    
    {          
        result = n;     
    }     
    else     
    {          
        it = g\_Cache.find(n-1);          
  
        if(it != g\_Cache.end())              
            result = it->second + gf(n);          
        else              
            result = f(n-1) + gf(n);     
    }     
  
    g\_Cache.insert(make\_pair(n, result));     
    return result;   
}   
  
int main()   
{     
    int i;     
  
    for(i = 2; f(i) != i; ++i)          
        ;     
  
    printf("%d\n", i);     
  
    int last = 1;     
    for(i = 2; (last += gf(i)) != i; ++i)          
        ;     
  
    printf("%d\n", i);     
    return 0;   
}