[JAVA] 백준 2749 - 피보나치 수 3

문제

https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

해결 방법

• 문제에서 주어진 n이 1,000,000,000,000,000,000 이하의 자연수
  • 반복문을 돌릴 수 없음
• 결과값은 피보나치 수를 1,000,000로 나눈 나머지이기 때문에 int 형으로도 처리할 수 있음
• 고민해본 결과, 피보나치 수를 1,000,000으로 나눈 나머지가 언젠가는 반복될 것이라는 생각이 들었음
• 코딩을 통해 반복되는 수를 찾음
  1. 피보나치 1,500,000 번째 숫자를 1,000,000으로 나눈 나머지는 0이었고,
  2. 피보나치 1,500,001 번째 숫자를 1,000,000으로 나눈 나머지는 1이었음
  3. 따라서 n을 입력받아 1,500,000 으로 나눈 나머지 번째 값을 구해주면 됨

코드

import java.util.Scanner;

public class p2749 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = (int) (sc.nextLong() % 1500000);

        if(n == 0) {
            System.out.println(0);
        } else if(n == 1) {
            System.out.println(1);
        } else {
            int a = 0;
            int b = 1;
            int c = 0;

            for(int i = 2 ; i <= n ; i ++) {
                c = (a + b) % 1000000;
                a = b; b = c;
            }
            System.out.println(c);
        }
    }
}

 반복구간을 찾는 코드

int i = 1;
int a = 0;
int b = 1;
int c = 0;

while(true) {
    c = (b + a) % 1000000;
    if(c == 1 && b == 0) {
        System.out.println(i); // 1500000 출력
        break;
    }
    a = b; 
    b = c; 
    i ++;
}