목록2026/03/07 (1)

승코딩당당당

[C++] 백준 9471: 피사노 주기

문제[C++] 백준 9471: 피사노 주기 SILVER 4https://www.acmicpc.net/problem/9471 접근 방법백준 9471번은 피사노 주기(Pisano Period) 를 구하는 문제다.피보나치 수열을 어떤 정수 m으로 나눈 나머지를 계속 계산하면 수열이 일정한 주기를 가지고 반복된다.이 반복되는 길이를 피사노 주기라고 한다. 예를 들어, 피보나치 수열을 3으로 나눈 나머지를 보면1 1 2 0 2 2 1 0 1 1 ...이렇게 특정 구간 이후부터 동일한 패턴이 반복된다.이 반복되는 길이가 바로 피사노 주기 k(m) 이다. 상세 아이디피사노 주기는 다음 성질을 가진다.k(m) ≤ m² − 1 즉, 최대 m^2번 정도만 확인하면 반드시 주기가 발견된다.그래서 반복문을 m * m 범위까..
PS/BOJ 2026. 3. 7. 23:33
이전 Prev 1 Next 다음