juhyun16   3년 전

저도 Sqrt Decomposition 으로 시도했었고 시간초과를 여러번 받았었어요.

시간초과를 해결할 수 있는데, 우선 용어정리부터 해보겠습니다.

1) 블록 사이즈 : 하나의 버킷이 관리하는 배열의 크기.

2) 버킷 갯수 : 배열을 "블록 사이즈" 만큼 나누었을 때, 생기는 버킷의 갯수.

예시)

배열 A의 크기가 100이라 가정.

- 블록 사이즈 : 20으로 잡으면, 버킷은 5개가 됨

- 블록 사이즈 : 30으로 잡으면, 버킷은 4개가 됨

- 블록 사이즈 : 50으로 잡으면, 버킷은 2개가 됨

================================================================

문제로 돌아와서,,, N의 크기가 10만인데 블록 사이즈를 루트(10만)에 가깝게 잡지말고 좀 더 크게 해야하더라고요.

블록 사이즈를 1,500 이런식으로 크게 잡고 버킷의 갯수를 줄이는 방식으로 하니 시간초과가 해결됐습니다.

유사문제인 수열과 쿼리3(https://www.acmicpc.net/proble...) 도 블록 사이즈를 크게 잡는 방식으로 풀 수 있더라고요.

수열과 쿼리18(https://www.acmicpc.net/proble...) 은 시간제한이 좀 더 넉넉해서 블록 사이즈를 루트(10만)에 가깝게 잡아도 시간 내에 해결되었습니다~

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