dmsrb1002   5년 전

단순 배열을 이용하여 각각의 라이트에 대해 배열을 하나씩 채워넣었더니 시간초과가 나네요.

어떤 알고리즘이 사용되어야 할까요??

chogahui05   5년 전

2가지 방법이 있습니다.

(1) 각각의 Light에 대해서 2차원으로 변형한 후에 누적합으로 구하기.

(2) 2차원 구간에 대한 정보를 Seg Tree에 갱신하면서 구하기.

예를 들어서

1 7

2 3

2 6

3 8

5 6

3 6

이라는 점이 있고

우리가 구해야 하는 것이 x<=a, y<=b 범위에 있는 점의 갯수를 구하기. 라고 해 봅시다. 그러한 경우

일단 1차원을 줄이기 위해서, 정렬을 시킵니다. 2차 정렬 기준으로 y축을 오름차순으로 정렬합시다.

1 7

2 3

2 6

3 6

3 8

5 6


이렇게 한 경우, x<=a이고 y<=b 범위에 있는 점의 갯수를 구한다. 라고 했을 때. a값에 따라서

어느 점까지 seg에 넣을지를 결정할 수 있습니다. 만약에 a = 2라고 해 봅시다. 그러면, x = 3이나 x = 5에 대한 정보를 넣을 필요는 없습니다.

x = 1과 x = 2에 대한 정보만 넣으면 됩니다. 문제 특성상, 그렇게만 해도 충분할 거에요.

dmsrb1002   5년 전

항상 답변 감사합니다~

저는 첫번째 방법을 이용해서 풀었습니다. 아직 seg tree에 대한 개념이 부족해서 공부를 더 해보고 다시 풀어보려고 합니다!


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