모르도르 (Mordor), 오크 (Orc) 같은 고유명사의 사용으로 보아 반지의 제왕을 패러디한 문제라는 걸 알 수 있습니다.
본문을 요약하면, 오크들의 숫자는 피보나치 수열의 규칙 ( $ F_{n+2}=F_{n+1}+F_{n} $ ) 을 따라갑니다.
이때 $ F_{0} $과 $ F_{1} $ 의 값을 줄 테니 (각각 a와 b), $ F_{c+1} $의 값을 구하라는 것입니다. (c가 주어짐)
int 범위를 넘는 답이 나오지 않고, 딱히 mod 값을 구하라는 문구도 없습니다.
코드를 구하기 전에, 간단히 방법을 설명하자면
$ \begin{pmatrix} F_{n+1} & F_{n} \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} F_{n} & F_{n-1} \\ 0 & 0 \end{pmatrix} \times \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} $ 이므로,
$ \begin{pmatrix} F_{n+1} & F_{n} \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} F_{1} & F_{0} \\ 0 & 0 \end{pmatrix} \times \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} $ 이 성립합니다.
따라서 다음과 같이 코드를 짜면 됩니다.
#include <stdio.h>
typedef struct {
int array[2][2];
} Matrix;
Matrix matrix_multiply (Matrix A, Matrix B);
Matrix matrix_power (Matrix A, int K);
int main() {
int a, b, c;
while(1) {
scanf("%d %d %d", &a, &b, &c);
if (a == 0 && b == 0 && c == 0) {
break;
}
Matrix Fibonacci;
Fibonacci.array[0][0] = b, Fibonacci.array[0][1] = a;
Fibonacci.array[1][0] = Fibonacci.array[1][1] = 0;
Matrix Base;
Base.array[0][0] = Base.array[0][1] = Base.array[1][0] = 1;
Base.array[1][1] = 0;
Base = matrix_power (Base, c);
Fibonacci = matrix_multiply (Fibonacci, Base);
printf("%d\n", Fibonacci.array[0][0]);
}
return 0;
}
Matrix matrix_multiply (Matrix A, Matrix B) {
Matrix result;
int i, j, k;
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
result.array[i][j] = 0;
for (k = 0; k < 2; k++) {
result.array[i][j] += (A.array[i][k] * B.array[k][j]);
}
}
}
return result;
}
Matrix matrix_power (Matrix A, int K) {
Matrix result;
result.array[0][0] = result.array[1][1] = 1;
result.array[1][0] = result.array[0][1] = 0;
while (K > 0) {
if (K & 1) {
result = matrix_multiply (result, A);
}
A = matrix_multiply (A, A);
K >>= 1;
}
return result;
}
(C11, 1116KB, 0ms, 제출번호 25773705)
조금 더 신경 써서 long long 범위까지 늘리거나, modulo가 존재하거나 했으면 골드까지 올라갔을 법한 문제입니다.
영어+스토리텔링 문제라서 그런지 인기가 상당히 없는 문제였습니다.
개인적으로는 지금 상태로도 골드5 정도는 충분히 가능하다고 생각하는데...
'분할 정복을 이용한 거듭제곱 > 행렬 거듭제곱' 카테고리의 다른 글
백준 15712번: 등비수열 (0) | 2021.01.29 |
---|---|
백준 14440번: 정수 수열 (0) | 2021.01.29 |
백준 11440번: 피보나치 수의 제곱의 합 (0) | 2021.01.29 |
백준 11443번: 짝수번째 피보나치 수의 합 (0) | 2021.01.29 |
백준 11442번: 홀수번째 피보나치 수의 합 (0) | 2021.01.29 |