백준 9471 피사노 주기

2020. 9. 18. 20:29·알고리즘/BOJ

www.acmicpc.net/problem/9471

 

9471번: 피사노 주기

첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000)

www.acmicpc.net

피보나치수열을 m으로 나누면 일정한 주기를 띄게 되는데 그 주기의 길이를 찾는 문제이다.

우선 주기마다 규칙이 있을 거라 판단하고 몇 개의 케이스를 돌려보았다.

 

 

7로 나눈 주기
10으로 나눈 주기

이 외에도 몇개를 더 살펴봤지만 1, 0 숫자가 나온 뒤에 다시 주기가 나오는 것을 확인할 수 있다.

 

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int tc, n, m;
	cin >> tc;

	while (tc--) {
		cin >> n >> m;

		int m1 = 0, m2 = 1, cnt = 0;

		do {
			int tmp = m1;
			m1 = m2;
			m2 = (tmp + m1) % m;
			cnt++;
		} while (m1 != 0 || m2 != 1 || !cnt);

		cout << n << ' ' << cnt << '\n';
	}

	return 0;
}

위와 같은 코드로 m1 이 0이고 m2가 1인 경우로 다시 돌아오면 그 길이가 주기라고 할 수 있다.

'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 11444 피보나치 수 6  (0) 2020.09.18
BOJ 2749 피보나치 수 3  (0) 2020.09.18
BOJ 1780 종이의 개수  (0) 2020.09.18
BOJ 1992 쿼드트리  (0) 2020.09.18
BOJ 10830 행렬 제곱  (0) 2020.09.16
'알고리즘/BOJ' 카테고리의 다른 글
  • BOJ 11444 피보나치 수 6
  • BOJ 2749 피보나치 수 3
  • BOJ 1780 종이의 개수
  • BOJ 1992 쿼드트리
khyu2
khyu2
  • khyu2
    dev log
    khyu2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘
        • BOJ
        • Programmers
        • Algorithm
        • SWEA
      • 개발
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    소수
    유니온 파인드
    프로그래머스
    SWEA
    이분탐색
    행렬 제곱
    dp
    dfs
    다익스트라
    피사노 주기
    GREEDY
    코딩테스트 연습
    완전 탐색
    BOJ
    크루스칼
    조합
    이분 탐색
    트리
    냅색
    분할 정복
    MST
    완전탐색
    시뮬레이션
    구현
    BFS
    큐
    피보나치 수
    알고리즘
    우선순위 큐
    팰린드롬
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
khyu2
백준 9471 피사노 주기
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.