-문제설명
준하는 번식력이 아주 뛰어난 곰팡이를 배양하는데 성공했습니다. 이 곰팡이는 포자 상태에서 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;
}
실행은 되지만 실패가 뜨는 것으로 보아 시간초과가 발생했을 것으로 예상되어서 찾아보았고
그래서 발견한게 행렬거듭제곱!
피보나치 수열을 효율적으로 계산하는 방법이 행렬거듭제곱이라고 합니다.
시간 복잡도
- 행렬 거듭제곱은 이진 거듭제곱법을 사용하여 의 시간 복잡도로 계산
- 따라서 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]);
}
}
'코딩 알고리즘 스터디' 카테고리의 다른 글
프로그래머스 중급 블로그 (0) | 2024.12.04 |
---|---|
코딩마스터스 (고급) 작곡 프로그램 (1) | 2024.12.03 |
프로그래머스 Lv.3 정수삼각형 (0) | 2024.11.11 |
프로그래머스 Lv.2 롤케이크 자르기 (0) | 2024.11.11 |
프로그래머스 Lv.3 보석 쇼핑 (2) | 2024.10.28 |