코딩마스터스 (중급) 곰팡이

-문제설명

준하는 번식력이 아주 뛰어난 곰팡이를 배양하는데 성공했습니다. 이 곰팡이는 포자 상태에서 1분이 지나면 번식 가능한 상태가 됩니다. 번식 가능한 곰팡이는 그 이후 매 1분마다 1개의 포자를 만들어 냅니다.

예를 들어, 0분 시점에 곰팡이 포자 1개가 있다고 할 때, 3분까지의 곰팡이 수는 다음과 같습니다.

0분 : 곰팡이 포자 1개

1분 : 번식 가능한 곰팡이 1개

2분 : 번식 가능한 곰팡이 1개, 곰팡이 포자 1개

3분 : 번식 가능한 곰팡이 2개, 곰팡이 포자 1개

0분 시점에 곰팡이 포자 1개가 있을 때, N분 후에 곰팡이 포자와 번식 가능한 곰팡이를 합친 총 곰팡이 수를 계산하는 프로그램을 작성해 주세요.

 

- 입출력 예

입력 #1

3

입력 #2

6

 

- 입력값 설명

• 첫째 줄에 N이 주어집니다.
• (1 ≤ N ≤ 1,000,000,000,000)

출력 #1

3

출력 #2

13

 

- 출력값 설명

N분 후에 총 곰팡이 수를 출력합니다.

곰팡이가 너무 많아질 수 있으므로, 1,000,000,007로 나눈 나머지를 출력합니다.

 

- 풀이과정

분마다 늘어나는 곰팡이는 1분 : 1포자  2분 : 1곰팡이, 1포자  3분 : 2곰팡이, 1포자와 같다.

이러한 곰팡이의 증식 규칙을 보면 피보나치 수열과 유사하다는 생각이 들었습니다.

하지만 간단하게 반복문으로 fibonacci로 만들었다가 실패만 떳습니다..

for (long i = 2; i <= n; i++) {
    current = (prev1 + prev2) % MOD;
    prev2 = prev1;
    prev1 = current;
}

 

실행은 되지만 실패가 뜨는 것으로 보아 시간초과가 발생했을 것으로 예상되어서 찾아보았고

결과도 안나옴..^^

 

그래서 발견한게 행렬거듭제곱!

피보나치 수열을 효율적으로 계산하는 방법이 행렬거듭제곱이라고 합니다.

 

시간 복잡도

• 행렬 거듭제곱은 이진 거듭제곱법을 사용하여 O(logN)의 시간 복잡도로 계산
• 따라서 n이 10^{12}처럼 커도 효율적으로 계산 가능

짝수인 수와 홀수를 각각 다르게 계산함으로써 시간복잡도를 반으로 줄일 수 있는 것인데요,

홀수이면 짝수에서 한번만 더하면 되니까 n이 클수록 더욱 효율적으로 계산이 가능한 것이지요!

록현 반장님 설명

 

정말 감사하게도 스터디원분께서 그림을 그려서 설명해주셔서 사진을 올려봅니다.

import java.io.*;
import java.util.*; 

public class Main {
    public static void main(String[] args) throws IOException { 
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        int MOD = 1_000_000_007;

        if (n == 0) {
            System.out.println(1);
            return;
        }
        if (n == 1) {
            System.out.println(1);
            return;
        }

        // 피보나치 행렬
        long[][] matrix = { 
            {1, 1},
            {1, 0}
        };
        
        // 단위행렬
        long[][] result = { 
            {1, 0},
            {0, 1}
        };

        while (n > 0) {
            // 홀수
            if (n % 2 == 1) { 
                long[][] temp = new long[2][2];
                temp[0][0] = (result[0][0] * matrix[0][0] + result[0][1] * matrix[1][0]) % MOD;
                temp[0][1] = (result[0][0] * matrix[0][1] + result[0][1] * matrix[1][1]) % MOD;
                temp[1][0] = (result[1][0] * matrix[0][0] + result[1][1] * matrix[1][0]) % MOD;
                temp[1][1] = (result[1][0] * matrix[0][1] + result[1][1] * matrix[1][1]) % MOD;
                result = temp;
            }
            // 짝수
            long[][] temp = new long[2][2];
            temp[0][0] = (matrix[0][0] * matrix[0][0] + matrix[0][1] * matrix[1][0]) % MOD;
            temp[0][1] = (matrix[0][0] * matrix[0][1] + matrix[0][1] * matrix[1][1]) % MOD;
            temp[1][0] = (matrix[1][0] * matrix[0][0] + matrix[1][1] * matrix[1][0]) % MOD;
            temp[1][1] = (matrix[1][0] * matrix[0][1] + matrix[1][1] * matrix[1][1]) % MOD;
            matrix = temp;

            n /= 2;
        }
        System.out.println(result[0][0]);
    }
}

감격스러운 성공!