[프로그래머스] 피보나치 수

link

문제의 키 포인트 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

def solution(n):
    answer = 0
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b
    return a%1234567

1234567을 사용 한 이유

일반적인 프로그래밍 언어는 CPU에서 제공하는 최소 읽기 단위(word라고 하는 것으로 기억합니다)를 기준으로 변수의 범위를 지정합니다. 일반적인 x86 시스템(인텔이나 AMD가 만든 그거입니다)은 word의 크기가 4byte라고 가정하며, 그렇기 때문에 int라는 자료형은 -2,147,483,648 ~ 2,147,483,647까지의 값만을 표현할 수 있습니다(계산해보시면 총 숫자 개수가232 개입니다. 1 바이트는 8비트니까요)

그런데 피보나치 수는 엄청나게 빠르게 증가합니다. 44번째 피보나치 수만 가도 2,971,215,073로 int 범위를 넘어버립니다. 이대로면 피보나치의 수를 구하라는 문제는 int를 사용할 수가 없겠지요? 그런데 우리에게는 고마운 성질이 있습니다. 숫자 A, B, C가 있다고 하면 (A + B) % C의 값은 ( ( A % C ) + ( B % C) ) % C와 같다는 성질입니다. 이 외에도 여러가지 있는데 알고 싶으시다면 모듈러 연산의 성질을 검색해보세요.

그래서 문제가 1234567로 나눈 나머지를 출력하라고 하는 겁니다. 조금만 숫자가 커져도 피보나치는 int로 표현할 수 있는 범위를 넘겨버리는데, 매번 1234567로 나눈 나머지만을 저장하는 것은 int의 범위에서 가뿐하니까요(당연하다면 당연하지만, 1234567로 나눈 나머지는 항상 1234567보다 작습니다).

이 글을 읽고 계시는 분이 문제를 풀 수 없었던 이유는, n번째 피보나치 수라고 구한 숫자가, 이미 int의 범위를 넘긴 상태라 엉망진창이 된 상태일 것이고, 이것을 1234567로 나눈다고 한들 정확한 값을 구하는 것은 불가능했기 때문입니다.

한줄요약: 문제에서 1234567로 나눈 나머지를 정답으로 내놓으라는 것은 문제를 꼰 것이 아니라 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려이며, 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다.