블로그 이사 중입니다 >> gumgood.github.io

3089 네잎 클로버를 찾아서 본문

Problem Solving/문제 풀이

3089 네잎 클로버를 찾아서

gumgood 2018. 11. 7. 11:32

C++11


전처리를 통해 i번째 좌표의 상하좌우에 몇 번째 좌표가 있는지 저장해둔다. O(NlogN)


그 정보를 바탕으로 외계인의 명령을 따라간다. O(M)


O(NlogN + M)



전처리의 아이디어는 다음과 같다.


 1) X좌표 기준으로 sorting했을 때 연속된 두 점의 x좌표가 같다면 두 점은 상하관계에 있다


 2) y좌표 기준으로 sorting했을 때 연속된 두 점의 y좌표가 같다면 두 점은 좌우관계에 있다

'Problem Solving > 문제 풀이' 카테고리의 다른 글

2479 경로 찾기  (0) 2018.11.07
13901 로봇  (0) 2018.11.07
3089 네잎 클로버를 찾아서  (0) 2018.11.07
6593 상범 빌딩  (0) 2018.11.07
4485 녹색 옷 입은 애가 젤다지?  (0) 2018.11.07
1261 알고스팟  (0) 2018.11.07
0 Comments
댓글쓰기 폼