반응형 Problem Solving/Divide and Conquer2 [분할 정복/ 파이썬] 백준 11444번 : 피보나치 수 6 / 골드 3 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net dp로 잘 알려진 피보나치 문제지만, 이 문제에선 n이 정말 큰 수로 주어지기 때문에 조금 다른 방법을 써야한다. 도가뉴 항등식이라고 있다. n번째 피보나치 수를 a(n)이라 하면, a(2n) = a(n)[a(n) + 2a(n-1)] a(2n-1) = a(n)**2 + a(n-1)**2 가 성립한다. 따라서 n이 아무리 커도 log(n) 시간에 문제를 해결할 수 있기 때문에 이 문제를 풀 수가 있다. import collections n = int(input()) m = 1.. 2021. 12. 6. [분할 정복] 백준 10830번: 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net import collections n, b = map(int, input().split()) a = [] for i in range(n): a.append(list(map(int, input().split()))) dct = collections.defaultdict(list) dct[1] = a def cross(m1, m2, n1, n2): result = [[0 for _ in range(n)] for _.. 2021. 9. 8. 이전 1 다음 반응형
