2465번 - 줄 세우기
줄세우는 과정에서 b[i]를 계산하는데 O(n^2)이라 n이 큰경우에 시간초과가 되네요
b[i]는 b[i+1] ~ b[n]의 값에 따라 위치가 정해지는거 같아서 n-i개를 읽어야 할것 같은데
다른방식으로 바꿔서 계산할 수 있을까요 ?
Brute force로는 N^2이죠.
구간트리를 이용해서 푸셔야 합니다.
저도 하루종일 삽질하다 겨우 풀었네요 ㅠ
댓글을 작성하려면 로그인해야 합니다.
yujinee 8년 전
줄세우는 과정에서 b[i]를 계산하는데 O(n^2)이라 n이 큰경우에 시간초과가 되네요
b[i]는 b[i+1] ~ b[n]의 값에 따라 위치가 정해지는거 같아서 n-i개를 읽어야 할것 같은데
다른방식으로 바꿔서 계산할 수 있을까요 ?