행렬제곱2 BOJ G2 2749 피보나치수3 JAVA 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 읽기 일단 피보나치를 푸는 내가 아는 가장 간단한 방법.. DP.. 그거 말고는 생각이 나지 않았는데, 문제에서 주어지는 N의 크기는 엄청났다. 무려 10의 18승..!! 저번에 풀었던 power의 분할 정복 처럼 로그를 씌우지 않고는 불가능한 거 아닌가? 생각이 들면서 전혀 감이 잡히지 않았고, DP로 코드를 한 번 짜봤지만 당연하게도 N의 최대 범위를 넣으니 응답이 없었다.. 그래서 질문 게시판을 참고했다. 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = 0$ $F_1 = 1$ $F_n.. 2024. 1. 18. BOJ G4 10830 행렬제곱 JAVA 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 어제 풀었던 문제와 비슷한 부분이 있어서 분할 정복을 빠르게 떠올렸다. 행렬 곱 식을 통해 문제를 풀었다. 문제 풀기 문제를 요약하면 행렬의 거듭 제곱 문제이다. 행렬 내가 행렬 곱을 제대로 알고 있는지 몰라서 일단 연습해봤는데 맞는 것 같다. 이렇게 계산할 수 있고, 다음과 같은 식을 얻을 수 있다. 분할 정복을 이용한 거듭 제곱 → O(logN) 두 번째로 고려할 것은 B의 크기이다. N도 최대 5로 작고, 행렬의 원소도 1000 이하이므로 작은데, B의 크기가 .. 2024. 1. 16. 이전 1 다음
