Overflow 문제. (피보나치 수)
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한 사항
- n은 2 이상 100,000 이하인 자연수입니다.
1. 실수 코드
굉장히 쉬워 보이는 문제..... 낮은 숫자라면 잘 돌아가지만 숫자가 조금 만 커지면,...
흠......
이걸 어케 하지............
%1234567 을 해본다.
출처 :
https://school.programmers.co.kr/questions/11991?question=11991
이유는
int라는 자료형은 -2,147,483,648 ~ 2,147,483,647까지의 값만을 표현할 수 있습니다
숫자 개수가2^32 개입니다. 1 바이트는 8비트니까요)
숫자 A, B, C가 있다고 하면 (A + B) % C의 값은 ( ( A % C ) + ( B % C) ) % C와 같다는 성질입니다. 이 외에도 여러가지 있는데 알고 싶으시다면 모듈러 연산의 성질을 검색해보세요.
그래서 문제가 1234567로 나눈 나머지를 출력하라고 하는 겁니다. 조금만 숫자가 커져도 피보나치는 int로 표현할 수 있는 범위를 넘겨버리는데, 매번 1234567로 나눈 나머지만을 저장하는 것은 int의 범위에서 가뿐하니까요(당연하다면 당연하지만, 1234567로 나눈 나머지는 항상 1234567보다 작습니다).
n번째 피보나치 수라고 구한 숫자가, 이미 int의 범위를 넘긴 상태라 엉망진창이 된 상태일 것이고,
이것을 1234567로 나눈다고 한들 정확한 값을 구하는 것은 불가능했기 때문입니다.
지문이 명백히 잘못된 것이 아니라, 이미 잘못된 값의 나머지 값을 답으로 내놓으셨으니, 정답이 아니라고 한 것입니다.
요약하자면! 열심히 피보나치 수를 계산한 다음에 나올 수를 1234567로 나눈 나머지는 각 연산을 수행할 때마다
1234567로 나누는 것과 완벽하게 동일한 숫자가 나온다는 겁니다!!
절대 문제 설명이 잘못된 게 아니에요!!!
혹시나 이것이 믿겨지지 않는다면 자체적으로 자료형 구분 없이 큰 수를 저장할 수 있는 Python등의 언어를 사용해서 오류가 났던 그대로 구현해보세요. 전부 정답 처리 될 것입니다.
한줄요약: 문제에서 1234567로 나눈 나머지를 정답으로 내놓으라는 것은 문제를 꼰 것이 아니라 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려이며, 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다.
그래도 여전히 몇개의 오류가 난다...
자세히 보니 정답을 낼때도 같게 해야 한드는걸 깜밖했다...
아니면 그냥 // N+1 까지 받는것
