qktlf789456   3년 전

맞은분들 코드를 확인해봤는데 O(lgN) 방식의 풀이인 것 같습니다.

N승 문제 구하기랑 약간 비슷한 것 같은데 풀이가 이해가 안 가네요 ㅠ 

어떤식의 DP로 구할 수 있는건가요?

pl0892029   3년 전

N승 구하기를 logN에 하는 것은 쉬운 일입니다.

그리고 같은 행렬을 N승하는 것은 N승 구하기의 연장선임을 이해하는 것 또한 쉬운 일입니다.

피보나치 수열을 피보나치 행렬로 해석하고(이 또한 유도는 쉬운 일이나, 정형화된 유도가 많기 떄문에 그대로 따라가셔도 됩니다.), 행렬의 N승을 통해 N번째 피보나치 수를 구하시면 됩니다.

시간복잡도는 예상하셨던 것과 같이 O(logN)입니다.

댓글을 작성하려면 로그인해야 합니다.