juice500   1년 전

문제를 접근할 당시 Divide & Conquer 방식으로 중간에 있는 원소를 포함하는 경우를 계산하고 아닌 경우를 해당 원소 왼쪽과 오른쪽 구간으로 분할하여 푸는 방식을 택했습니다.

중간에 있는 원소를 포함한 정답을 계산하는 함수가 msum(), 분할하여 비교하는 함수가 tsum()입니다.

소스코드에서 msum()함수의 시간복잡도가 O(n)이고, tsum()함수의 시간복잡도는 O(n*log2(n))인 것 같은데 왜 시간초과가 나는지 모르겠습니다.


흐.. 아무리 봐도 잘 모르겠네요 엉엉 불쌍한 중생을 구원해주세요ㅠ_ㅜ

cubelover   1년 전

16~23줄이 전체적으로 이상합니다. 다음과 같은 데이터에서 TLE가 납니다.


100000 100000 99999 99998 99997 ... 2 1

0

juice500   1년 전

흐.. 그렇군요 감사합니다

juice500   1년 전

주신 테스트케이스를 돌려보니 이리저리 고쳐봐도 20초정도 걸리는 것 같습니다

아무래도 이 방법은 아닌가봅니다ㅜ_ㅠ 감사합니다


cubelover   1년 전

방법이 틀린 것은 아닙니다. 제가 드린 케이스에서 오래 걸리는 이유가 i<l 인데도 17,18줄을 실행시켜서인데, i<l 인 경우를 먼저 체크해주는 식으로 아래처럼 고치면 됩니다.

juice500   1년 전

우와 감사합니다!!!! 저래서 시간초과였다니!

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