반응형 분할정복2 [C/C++] 백준 #2086 피보나치 수의 합(분할정복) 이번 문제는 피보나치 수열들의 합을 계산하는 것입니다. 언뜻, 피보나치 수열을 구해서 그 합을 구해야 할 것으로 생각할 수 있습니다. 수학식을 유도하는 것이 어려워서인지, 문제의 난이도는 Gold I 단계입니다. https://www.acmicpc.net/problem/2086 2086번: 피보나치 수의 합 제 1항과 제 2항을 1이라 하고, 제 3항부터는 앞의 두 항의 합을 취하는 수열을 피보나치(fibonacci) 수열이라고 한다. 예를 들어 제 3항은 2이며, 제 4항은 3이다. 피보나치 수열의 a번째 항부터 b번째 www.acmicpc.net 조금 생각해보면, 이 수열도 피보나치 수열과 다르지 않다는 것을 알 수 있습니다. 수학적으로 점화식을 이용해서 풀이를 하는 것이라서, 다소 생소할 수가 있습.. 2023. 3. 28. [C/C++] 백준 #1780 종이의 개수(분할정복) 이번 문제는 무조건 분할을 한 후에, 그 결과를 토대로 결정을 하게 하는 문제입니다. 결국 분할 정복 문제입니다. 9개로 나누어 그 결과가 모두 같으면, 숫자의 종이를 합치는 것이죠. 원래의 문제는 하나의 종이에 모두 같은 숫자가 있다면 분할하지 않는 것이지만, 이렇게 하면, 상당히 많이 숫자를 세어야 합니다. 종이에 써져있는 숫자의 갯수가 최대 4백만개가 되므로, 숫자가 같은지 검사하는 것은 매우 비효율적입니다. 제가 사용한 방식은 무조건 분할한 다음, 9개가 모두 같은지 검사하여 같으면 종이를 합치는 것이죠. 시간 효율을 따져본다면, 다음과 같이 점화식을 낼 수 있습니다. \[ T(1) = 1 \] \[ T(n) = 9T(n/3) + 1 \] 형태가 되어서 \(O(n^2)\) 으로 볼 수가 있습니다... 2022. 10. 20. 이전 1 다음 728x90
