pseojin1115   2년 전

제가 분할정복 코드를 잘못 짠 것인지, 아니면 다른 방법을 선택해야 하는지 궁금합니다!

gs18103   2년 전

시간복잡도가 n^2 log n 인 것 같습니다. 분할정복 코드 안에서 최대 e - s번 calculate 함수를 호출하는데 또 calculate 함수가 e -s번 계산을 합니다.

gs18103   2년 전

두 구간으로 나눈 후 두 구간에 모두 걸친 구간들을 계산할때, 구간 길이를 바꾸면서 현재 구간의 그 계산값을 그때그때 바꿔주먄 n log n 만에 풀 수 있을 것으로 보입니다. 구간 길이를 바꿀때마다 구간 전체에 대한 계산값을 다시 계산하느라 오래 걸려요

gs18103   2년 전

또 사족을 붙이자면 #include <algorithm>을 하면 std::max와 std::min을 사용하실 수 있어 조금 더 편하실 거에요

pseojin1115   2년 전

자세한 답변 너무 감사드립니다. 참고해서 꼭 문제를 해결 해보도록 하겠습니다! 

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