== approach == input space 로 볼때 최악의 경우가 1~10^100 일 수 있겠다는 생각을 하면서 뭔가 다른 공식이 있겠다 생각, 피보나치의 closed-form 을 근거로 해결할 방법에 대해 궁리해보다. a,b 구간에 가장 가까울 f(x),f(y)를 각각 구하고, y-x 를 구하면 되리라고 생각. 하지만 3시간동안 고민했는데 잘 안되어서, 그냥 노가다 스러운 방법으로 풀기 시작. {{{~cpp def fibo(n): s=[1,2] if n in [1,2]: return s[n-1] i=2 while True: i+=1 fiboI=s[0]+s[1] if n==i: return fiboI s[0],s[1] = s[1], fiboI def howmany(a,b): i,count=1,0 while True: fiboI = fibo(i) if a < fiboI < b: count+=1 if fiboI > b: return count i+=1 print howmany(10,100) print howmany(1234567890,9876543210) print howmany(1,10**100) }}} 근데, a,b=(1,10^100) 로 해도 1초도 안걸린다. 처음에는 'big integer 를 만들어라!' 라는 문제가 아니라고 생각했는데, 풀고 나니 뭔가 허탈함. 글쌔. 출제자가 원한 답은 big integer emulation 이였을까. 흑.. 덤 : 피보나치 closed form {{{~cpp def fiboClosedForm(n): return int(((1+sqrt(5))**n - (1-sqrt(5))**n) / (2**n * sqrt(5))) }}} 기타 덤 : fibonacci 의 수열 당 자릿수 값. {{{ 1:1 2:1 3:1 4:1 5:1 6:2 7:2 8:2 9:2 10:2 11:3 12:3 13:3 14:3 15:3 16:4 17:4 18:4 19:4 20:5 21:5 22:5 23:5 24:5 25:6 26:6 27:6 28:6 29:6 30:7 31:7 32:7 33:7 34:7 35:8 36:8 37:8 38:8 39:9 40:9 41:9 42:9 43:9 44:10 45:10 46:10 47:10 48:10 49:11 50:11 51:11 52:11 53:11 54:12 55:12 56:12 57:12 58:12 59:13 60:13 61:13 62:13 63:14 64:14 65:14 66:14 67:14 68:15 69:15 70:15 71:15 72:15 73:16 74:16 75:16 76:16 77:16 78:17 79:17 80:17 81:17 82:17 83:18 84:18 85:18 86:18 87:19 88:19 89:19 90:19 91:19 92:20 93:20 94:20 95:20 96:20 97:21 98:21 99:21 100:21 101:21 102:22 103:22 104:22 105:22 106:23 107:23 108:23 109:23 110:23 111:24 112:24 113:24 114:24 115:24 116:25 117:25 118:25 119:25 120:25 121:26 122:26 123:26 124:26 125:26 126:27 127:27 128:27 129:27 130:28 131:28 132:28 133:28 134:28 135:29 136:29 137:29 138:29 139:29 140:30 141:30 142:30 143:30 144:30 145:31 146:31 147:31 148:31 149:31 150:32 151:32 152:32 153:32 154:33 155:33 156:33 157:33 158:33 159:34 160:34 161:34 162:34 163:34 164:35 165:35 166:35 167:35 168:35 169:36 170:36 171:36 172:36 173:37 174:37 175:37 176:37 177:37 178:38 179:38 180:38 181:38 182:38 183:39 184:39 185:39 186:39 187:39 188:40 189:40 190:40 191:40 192:40 193:41 194:41 195:41 196:41 197:42 198:42 199:42 200:42 201:42 202:43 203:43 204:43 205:43 206:43 207:44 208:44 209:44 210:44 211:44 212:45 213:45 214:45 215:45 216:46 217:46 218:46 219:46 220:46 221:47 222:47 223:47 224:47 225:47 226:48 227:48 228:48 229:48 230:48 231:49 232:49 233:49 234:49 235:49 236:50 237:50 238:50 239:50 240:51 241:51 242:51 243:51 244:51 245:52 246:52 247:52 248:52 249:52 250:53 251:53 252:53 253:53 254:53 255:54 256:54 257:54 258:54 259:54 260:55 261:55 262:55 263:55 264:56 265:56 266:56 267:56 268:56 269:57 270:57 271:57 272:57 273:57 274:58 275:58 276:58 277:58 278:58 279:59 280:59 281:59 282:59 283:60 284:60 285:60 286:60 287:60 288:61 289:61 290:61 291:61 292:61 293:62 294:62 295:62 296:62 297:62 298:63 299:63 300:63 301:63 302:63 303:64 304:64 305:64 306:64 307:65 308:65 309:65 310:65 311:65 312:66 313:66 314:66 315:66 316:66 317:67 318:67 319:67 320:67 321:67 322:68 323:68 324:68 325:68 326:68 327:69 328:69 329:69 330:69 331:70 332:70 333:70 334:70 335:70 336:71 337:71 338:71 339:71 340:71 341:72 342:72 343:72 344:72 345:72 346:73 347:73 348:73 349:73 350:74 351:74 352:74 353:74 354:74 355:75 356:75 357:75 358:75 359:75 360:76 361:76 362:76 363:76 364:76 365:77 366:77 367:77 368:77 369:77 370:78 371:78 372:78 373:78 374:79 375:79 376:79 377:79 378:79 379:80 380:80 381:80 382:80 383:80 384:81 385:81 386:81 387:81 388:81 389:82 390:82 391:82 392:82 393:82 394:83 395:83 396:83 397:83 398:84 399:84 400:84 401:84 402:84 403:85 404:85 405:85 406:85 407:85 408:86 409:86 410:86 411:86 412:86 413:87 414:87 415:87 416:87 417:88 418:88 419:88 420:88 421:88 422:89 423:89 424:89 425:89 426:89 427:90 428:90 429:90 430:90 431:90 432:91 433:91 434:91 435:91 436:91 437:92 438:92 439:92 440:92 441:93 442:93 443:93 444:93 445:93 446:94 447:94 448:94 449:94 450:94 451:95 452:95 453:95 454:95 455:95 456:96 457:96 458:96 459:96 460:96 461:97 462:97 463:97 464:97 465:98 466:98 467:98 468:98 469:98 470:99 471:99 472:99 473:99 474:99 475:100 476:100 477:100 478:100 479:100 480:101 481:101 482:101 483:101 484:102 485:102 486:102 487:102 488:102 489:103 490:103 491:103 492:103 493:103 494:104 495:104 496:104 497:104 498:104 499:105 }}} 피보나치 수가 굉장히 크게 늘어나는 수라는 점을 생각했더라면, input space 가 크더라도 fibo(n) 의 n 값이 커지지 않을 것이라는 것을 미리 알고 있었더라면 저런 고민을 안했을 것 같긴 하다. 하지만, 이러한 사전지식이 없는 가운데, 문제를 풀라고 한다면 어떻게 접근하는게 가장 좋았었을까. 고민된다. == 느낌 == * 컴퓨터의 속도를 무시하지 말자.; * 그럼에도 불구하고.. '정말 big integer 만들기' 문제였을까? 다시금 고민하게 되다. * closed form 과 관련하여 Generating Function 이 아직도 익숙치 않아서 mathworld 의 힘을 빌리다. GF 를 공부해야겠다. * 구간 계산과 관련, 'a 와 가장 가까운 fibonacci 값을 구하기' 는 반복문 돌리기 & if 로 비교 말고 다른 방법이 없을까? * bigint 를 지원하는 python 이나 matlab 같은 언어에서는 더 할일이 없는 문제. 내가 공식 궁리하는 동안 옆의 분이 matlab 으로 10분만에 풀어버리다. 흑.