드럼치는 프로그래머

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의 갯수를 발견할 수 있음을 깨달았다. 알고리즘을 간단히 설명하자면 각 자릿..