저장할 수 있는 수의 범위가 없다면 마지막이 아닌 중간에 %10007을 하는 것과 마지막에 %10007을 하는 것의 결과가 똑같음을 증명할 수 있습니다. 여기서는 수가 int 범위까지만 갈 수 있기 때문에 중간에 %10007을 안 하면 오히려 잘못된 값으로 오버플로우하게 됩니다.

허허... "중간에 %10007을 하는 것과 마지막에 %10007을 하는 것의 결과가 똑같음을 증명할 수 있"다는 사실을 제가 미쳐 몰랐네요. 단순히 알고리즘 이외에도 상식으로 알아둬야할 것들이 많네요. 잘 알아갑니다. 감사합니다. 

직감적으로 와닿지 않는다면 10진수의 수에서 일의 자리만 구하는 경우를 생각해보시면 됩니다. 덧셈과 곱셈만으로 이루어진 연산들에서 10의 자리를 넘어가는 건 아무 의미가 없으니, 매 연산마다 그 1의 자리 하나만 추적하고 있어도 결과는 똑같이 나옵니다. 마찬가지로, 이 수를 10007진수라고 생각하고 끝자리 한 자리만 추적해도 결과는 같습니다.

djm03178 님의 글을 잘 이해 못하겠는데요. 혹시 조금 쉽게 설명해주실수 있을까요???

int형 배열이 아닌 long 형 배열을 만들어서 최대입력값 1000을 넣으니

9079565065540428013 입니다.

long의 max_value는 9223372036854775807 고요.

그럼 마지막에 결과에 %10007 을 하면 정답이어야 하지 않나요???

역시 틀렸다고 나오네요.

문의드립니다.

그  9079565065540428013 라는 값 자체가 정답이 아니라 이미 수없이 많은 오버플로우를 거쳐서 나온 틀린 값입니다. 틀린 값에 뒤늦게 모듈로를 취해서는 정답이 될 수 없습니다.

참고로 N=1000일 때 실제 답은 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501입니다.

저도 이부분때문에 틀려서 질문드리는데요,

그러면 애초에 배열을 long long형으로 선언해도 오버플로우가 일어나니깐,

어쩔수 없이 배열에 저장하는 각 과정에서 10007로 mod연산을 해줘야 하는게 맞는거죠?

%는 다음과 같은 분배법칙이 성립합니다.

A few distributive properties of modulo are as follows: ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c.