skan1543   2년 전

ㅠㅠ 5480의 전함 문제랑 똑같은 솔루션으로 풀었습니다.

사정거리가 L 이고 i번째 동물의 x 좌표가 x[i], y좌표가 y[i]라면..

i번째 동물이 잡힐수 있는지는.. x[i]- (L-y[i]) 지점과 x[i]+(L-y[i]) 지점 사이에 사대가 있는지에 결정이 되므로

이를 인덱스트리로 찾아주는 방식으로 솔루션을 설계하였습니다.

모든 동물의 x[i]- (L-y[i]) 와 x[i]+(L-y[i]), 그리고 사대들의 x좌표들을 정렬하여..

인덱스트리에 깔아둔 후, 사대들의 x좌표에 해당하는 인덱스트리의 노드들만 위로 올라가면서 1을 업데이트 해주고..

인덱스트리에서 최솟값을 찾는 방식처럼  x[i]- (L-y[i]) 와 x[i]+(L-y[i]) 사이에 1이 있는지 찾아주는 방식인데요.

제생각엔.. nlogn의 솔루션인것같은데 TL이 나오네요.. 

채점중(10%)정도까지 밖에 가질 않습니다 ㅠㅠ.. 벡터에서 해주는 연산이 시간을 많이 잡아먹는걸까요? 

도움 부탁드립니다 ㅠㅠ

skan1543   2년 전

작성잔데요 ㅎㅎ

모든 동물들이 가지는 두 좌표가 다른 동물들과 전혀 겹치지 않고, 사대들과도 전혀 겹치지 않는다면..

벡터내에 들어가는 원소의 갯수는 30만개가 될것같습니다.

그나저나 주석이 없어서 읽으시는데 불편하실것같아서 죄송하네요ㅠㅠ

Nada   2년 전

인자로 vector<int> a 이렇게 넘기면 vector의 원소 전체를 복사해서 
TLE가 발생합니다. 그리고 BIT 크기도 작아서 런타임 에러까지 뜨네요. 

보통 원소개수x4를 해야합니다. 
위에 문제들을 해결하니 맞았네요.

추가적으로 vector를 인자를 넘기고 싶으면 참조변수나 포인터를 써서 넘기면 됩니다.

skan1543   2년 전

1/ 사랑합니다...ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

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