이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,000,000,000,000)인 걸 보아 절대 동적 계획법으로는 풀 수 없는 문제입니다. 이럴 땐, 점화식을 자세히 살펴보고, 분해해보아야 합니다. 수열의 n번째 항과, n-1번째 항을 위 아래로 나열해보면 과 같이 나타낼 수 있습니다. 그럼? 이것을 행렬로 나타내보면? 입니다. 오! 개쩔죠? 그럼? 이 점화식을 계속해서 나열해본다면! 이 될 것이고 이렇게 되니까, 피보나치 수열의 일반 행렬을 얻을 수 있습니다. n by n의 행렬을 곱하는 데엔 보통 O(n^3)의 시간 복잡도가 필요합니다.그리고 같은 행렬을 M번 곱하는 데는 O(Mn^3)의 시간이..
교환학생 온 3월부터 계속 느끼는 거지만, 여기 학식은 좀 비싼 것 같다. 거의 한 끼 먹을때마다 450-500엔 돈을 내야 한다. 아침을 먹지 않는다고 해도, 점심과 저녁을 먹으면 무려 1000엔 이상의 돈이 든다. 저녁을 5-6시 사이에 먹기 때문에, 10시쯤 출출해지는데 야식까지 먹으면 더 들 수 있다. 물론 저녁을 든든하게 먹으면 되지 않는가? 하는 의문도 있을 수 있지만 솔직히 500엔으로 일본에서 저녁을 배부르게, 든든하게 먹는다는 건 조금 어려운 것 같다. 그래서 요새는 점심 도시락을 싸볼까 생각중인데, 도시락을 싸오는 친구들을 보니 소풍날 애니에서 여주가 남주에게 거하게 한상 차려오는 것처럼 그렇게 거창하게 싸오는 것 갓진 않다. 요리를 내가 아얘 못하는 것도 아니고, 도시락을 싸서 다니면..
작성중