문제링크:11444번: 피보나치 수 6 (acmicpc.net) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 수는 알다시피 점화식이 Fn=Fn-1+Fn-2 로 표현될 수 있다. 그렇다면 N번째 피보나치 수를 구하려면 반드시 0부터 N까지 더해가며 An을 구해야 할까? 나도 처음에 그래야 할 것이라고 생각했지만 답은 아니었다. 답은 행렬의 곱셈을 이용하여 N번째 피보나치 수의 일반항을 구할 수 있다. 위 식을 보면 행렬 [[Fn],[Fn-1]] 행렬에 행렬 [[1,1],[1,0]]을 곱하면 각각 다음 피보나치 수가 나오는 것을 알 수 있다. 이는 행렬의 곱셈 과정 중 1행에는 ..