lg970325   4달 전

계속 고쳤는데

연산수도 별로 없는것 같은데 계속 시간초과가 뜨네요.....

 해결법을 알려주세요ㅠㅠ


yclock   4달 전

위 소스의 시간복잡도는 O(N2+NM)으로 NM이 최대 109까지 갈 수 있는 이 문제를 제한시간 내에 풀기는 어렵습니다.

부분합 문제의 접근 방법은 맞습니다. 그러나 합을 더하고 빼는 부분을 다르게 처리하면 O(1)으로 부분합을 구할 수 있습니다.

또는 첨부된 부분에서 다음과 같은 배열을 하나 선언해서 풀 수도 있습니다.

lg970325   4달 전

감사합니다!

문제의 부분을 고쳤더니 성공했습니다.

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