jane0013   1년 전

채점하면서 계속 시간초과가 뜨는데

다른 아이디어로 다시 짜야할까요..?

도무지 방법이 생각이 안나네요ㅠㅠ

Nada   1년 전

위 방법은 O(N^2) 솔루션인데

특정 값을 update하는 것과 일정 구간의 합을 O(logN) 만에 구하는 방법이 있습니다.

인덱스 트리나 펜윅트리를 이용해 구할 수 있는데 이 문제를 풀기 전에

https://www.acmicpc.net/problem/1275 이 문제를 풀고 도전하시는 게 나을 것 같아요.

이 방법을 이용해 O(NlogN)으로 문제를 풀 수 있습니다.


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