[김찬민]

1 1
9 1
10 2
50 6
500 157
5000 93162
10000 1224909
20000 23248264

아마 여기까지가 과제에 나온 방법으로 적당한 시간에 나올 한계일 것이고요,
이 밑으로는 정말 도전적인 계산을 하고 싶은 분들만 같이 확인해보시면 될 것 같아요.
(ex: 50000원권까지 테스트 하실 분들)
50000 2083485412
98765 84381023250 # 틀렸던 것을 주호영 님이 수정해주셨습니다.
100000 90569791408
200000 5482403668355
300000 69582450412242
400000 444195115484469
500000 1916371729026436
600000 6411908013859543
700000 17945489553485190
800000 43997485260084777
900000 97397388842519704
1000000 198793908274331371

-- 수정: 40만 이상 케이스 추가.
-- 수정2: 주호영 님의 테스트 케이스 반영.

[방정호]

테스트 케이스 감사합니다.
그런데 저는 2000만 넣어도 기다리기 짜증날만큼 엄청 오래걸리던데, 시간 얼마나 걸리셨는지 여쭤봐도 될까요?

그리고 조교님.
이 과제와 관련되서 수행시간이 이슈가 되는지도 알고 싶습니다.

[김찬민]

심심풀이로 이상한 짓을 좀 해서 저는 시간이 다음처럼 나옵니다.
50000은 0초
100000은 0.16초
300000은 7초

최적화하기 전에는 10000에 0.5초 정도 걸렸던 기억이지만, 2000에 시간이 오래 걸렸다고 해도 납득이 되긴 합니다.

[강동옥]

알고리즘의 효율성을 평가하는 과제가 아니기 때문에, 테스트 케이스의 수행 시간은 과제의 채점에 반영하지 않겠습니다만, 채점을 위해 실행 시간에 상한을 두도록 하겠습니다.

테스트 케이스의 크기는 3000 이하이며, 하나의 케이스를 돌리는데 걸리는 시간은 5분 이하인 것으로 정하겠습니다. 참고로, 과제 문서에서 제공하는 힌트를 참고해서 작성하시면 1초 이내로 마칠 수 있을 것입니다. 물론 이러한 알고리즘에 익숙하지 않으면 힌트가 쉽게 이해가 가지 않을 수 있지만, 가능한 힌트에 주어진 내용을 활용하시는 것을 추천드립니다.

[김용기]

조교님 말씀대로 효율적인 알고리즘 구현이 과제의 목적과는 무관하다고 생각되지만.
혹시 궁금하신 분들을 위해 최적화 팁을 드리자면

이 문제의 경우 재귀 호출 트리의 말단으로 갈수록 기하 급수적으로 호출 횟수가 늘어납니다.
실행기 구현에서 함수 호출에 대한 비용이 가장 비싸기 때문에 함수 호출 횟수를 줄이는 것이 관건입니다.
과제 문서의 예제를 그대로 옮겨 numch1(n)같은 상수함수까지 호출하도록 했다면 n이 작아도 실행 시간이 상당히 걸릴 것입니다.

가장 간단한 최적화는 numch1(n)을 상수로 치환하고, numch10(n)도 계산식으로 인라인화 하는 것입니다.
이렇게 하면 10000 까지는 3초 이내에 계산됩니다.

더 효과적인 최적화는 record를 이용해 리스트(또는 스택이나 힙)를 구현해, 이미 계산된 값들을 캐싱하도록 하는 것입니다.
더 공격적으로 인라인화를 numch100 / numch500 까지 해보는 것도 좋습니다. (이쯤되면 손 컴파일러...)

저의 경우는 n=300000일때 3초, 1000000일 때 1분 54초, 2000000일 때14분 50초가 걸렸습니다.

김찬민님 테스트 케이스에 추가합니다:
numch(2000000) = 4335775208959925125

[김찬민]

좋은 방법 설명해주셔서 감사합니다.

하지만 64비트 OCaml에서 Integer overflow 없이 계산할 수 있는 한계는 약 158만 정도라서, 200만은 방법에 따라 (특히 나눗셈을 이용한 경우) 답이 다르게 나올 수 있습니다. 혹시 200만의 값만 다르게 나온다고 해서 걱정하진 마세요.

[주호영]

위쪽 테스트 케이스 98765 틀렸습니다. (100000보다 크네요...)

저는 84381023250 나왔습니다.

혹시 뻘짓으로 인라인화를 numch1000까지 하시려는 분은...

제가 했는데 오버플로우떠서 failed ㅜㅜ

n500까지 해도 충분해요

[김찬민]

감사합니다. 수정했습니다!

[이성환]

저는 답이 잘 나오다가 20억 부근의 값에 도달하면 오버플로우가 난 것처럼 음의 값을 보여주던데 왜 그럴까요?
K- 언어의 구현상의 문제일까요?

정확히는 32bit integer 범위의 절반을 넘어가면 음의값( (2^32 -2) - result )을 보여주고 있습니다.

----

검색해보니 ocaml이 원래 31-bit integer를 갖는다는 글을 찾았습니다.
제가 32-bit ocaml을 설치해서 그런 모양이네요.