목록2026/03/08 (1)

승코딩당당당

[C++] 백준 2749: 피보나치 수 3

문제[C++] 백준 2749: 피보나치 수 3 GOLD 2https://www.acmicpc.net/problem/2749 접근 방법백준 2749번은 N번째 피보나치 수를 1,000,000으로 나눈 나머지를 구하는 문제다. 문제의 핵심은 N의 범위가 매우 크다는 것이다.N은 최대 10^18까지 주어질 수 있기 때문에, 단순히 피보나치 수열을 N까지 계산하는 방법으로는 해결할 수 없다. 이 문제를 해결하기 위해 피사노 주기(Pisano Period) 개념을 이용한다.피보나치 수열을 어떤 수 m으로 나눈 나머지는 반복되는 주기를 가진다.이 반복되는 길이를 피사노 주기라고 한다. 이 문제를 풀기 전에 백준 9471번 문제를 먼저 풀고 오는 것을 추천한다.관련 포스팅:https://xeungcoding.tis..
PS/BOJ 2026. 3. 8. 23:34
이전 Prev 1 Next 다음