괴짜 프로그래머의 일상사~@@

GLAT... :: 2006/09/18 01:13

양수 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; 
}

(0)

(0)

스폰서	글타래 관련 글 구글... (1025) 구글 통계(google analytic (1025) 최근 글 와우와 아이온의 차이...(46) 타이머 루틴의 예외는 왜(80) 체스 기보 뷰어 가젯(198) 2주간 인기 글 Scintilla, Notepad2, Note(438) 체스 기보 뷰어 가젯(198) 와우와 아이온의 차이...(46)