| [ QuizWit ] in KIDS 글 쓴 이(By): Sue (eXponent) 날 짜 (Date): 2006년 9월 20일 수요일 오후 04시 33분 29초 제 목(Title): Re: 오늘 신문에 난 문제 하나.. f(n).. 언제때 신문인지 모르겠는데, 우연히 오늘 신문을 보니 Google 입사 시험 문제라고 하면서, 아래 문제가 있더군요. 한번 풀어보세요. f(n) 은 자연수 n에 대해서 1부터 n 사이의 1의 갯수로 정의되어 있다. 즉 f(1) = 1, f(2) = 1, f(13) = 6 등등 f(n) = n 이 되는 최초의 수는 1이다. f(n) = n 이 되는 두번째 자연수는 얼마인가? -- 1자리수에서의 합 (1~9) 1 누적 f(9) = 1 2자리수에서의 합 (10~99) 1*9 + 10 누적 f(99) = 20 3자리수에서의 합 (100~999) 20 * 9 + 100 누적 f(999) = 300 4자리수에서의 합 (1000~9999) 300 * 9 + 1000 누적 f(9999) = 4000 5자리수에서의 합 4000 *9 + 10000 누적 f(99999) = 50000 6자리수에서의 합 50000 *9 + 100000 누적 f(999999) = 600000 그런데, 맨 앞자리 수가 1일때는 값이 계속 늘어나므로 f(1) = 1 f(19) = f(9)*2 + 10 = 12, f(199) = f(99)*2 + 100 = 140 f(1999) = f(999)*2 + 1000 = 1600 f(19999) = f(9999)*2 + 10000 = 18000 f(199999) = f(99999)*2 + 100000 = 200000 그러므로 199981에서 199990 까지의 수는 f(n) = n %%첫자리가 1이 아닌 경우에는 f(10^k - 1) < 10^k - 1이므로(k < 6) 검사하지 않아도 됨. ; Capture & Consider |