BOJ/피보나치 수 #6 baekjoon #10870 문제 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 �� www.acmicpc.net 이 문제는 피보나치 수 1과 완전 똑같다...................................... 입력 값의 차이 밖에 없는데 입력 값의 제한과 0을 입력 값으로 사용 가능한가 그 차이이다. 따라서 딱히 설명할 것은 없기에 소스코드와 피보나치 수 1의 링크만 올려 놓겠다. https://leening.tistory.com/8 소스코드 #i.. 2020. 6. 17. baekjoon #10826 문제 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 �� www.acmicpc.net 이 문제는 전 문제 '피보나치 수 3' 과는 다르게 수열 값이 long long int 자료형의 범위를 넘어 가지만 특정한 수의 나눈 나머지를 요구하지는 않는다. 해결책을 찾아보자. 해결 피보나치 수열은 F(n)은 이전 값과 전전 값의 합이다. 처음에는 어떻게 해결할지 감이 안잡혔었는데 큰 수 A + B를 풀어보고 나서 쉽게 해결할 수 있었다. ht.. 2020. 6. 17. baekjoon #2749 문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 입력 값의 제한이 10^18이나 된다. 피보나치 수열의 값이 당연히 long long int(64-bits)를 넘어갈 것이다. 그러므로 값을 줄일 방법으로 문자열을 이용하거나 다른 방법을 물색해야 하는데 이전에 포스팅 했던 피사노 주기를 이용해보도록 하겠다. 해결 이전에 포스팅한 https://leening.tistory.com/10 피사노 주기를 참고하기를 바란다. 간략하게 말하자면 피사노 주기는 피보나치 수열을 어떠한 수 M으로 나눈 나머지는 주기를 이룬다는.. 2020. 6. 17. baekjoon #9471 문제 https://www.acmicpc.net/problem/9471 9471번: 피사노 주기 문제 1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다. 예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다. n 1 2 3 4 5 6 7 8 9 10 F www.acmicpc.net 피보나치 수열을 어떠한 수로 나눈 나머지가 주기를 이룬다는 것이 피사노 주기이다. 이 문제는 주기를 구하는 문제인데 https://www.acmicpc.net/problem/2749 피보나치 3을 푸는데 도움을 줄 것이다. 해결 잊지 말아야 한다. 피사노 주기는! 피보나치 수열을 어떠한 수로 나눈 나머지가 주기를 이루는 것이다. 지금까지 작.. 2020. 6. 17. 이전 1 2 다음