annietibber 문제에 대해 힌트를 얻고싶습니다. suhee 먼저 문제 링크입니다. ANNIETIBBER 저는 annie/tibber의 좌표와 두 별의 좌표를 직선으로 연결하였을때 기울기 값을 계산하여 비교하는 방법을 이용했습니다. annie와 tibber의 좌표에서 두 별에 대한 각각의 기울기를 구한 후, 기울기 값을 비교했을때 부등호 방향이 다르게 나오면 count++ 하는 방식으로요. 하지만 제 풀이법으로는 시간초과가 나오네요.. 어떤 방식으로 문제를 풀어야 하는지 힌트를 얻고싶습니다. 9년 전
1개의 댓글이 있습니다. Being 점의 수가 10만개나 되니 아무래도 O(N^2) 알고리즘으로는 통과하기를 기대하긴 어렵죠. 힌트를 드리자면, 경우에 따라서는 시간 제한과 입력 제한으로부터 요구하는 알고리즘의 시간 복잡도를 예측할 수 있는데요, 이 경우는 O(N \lg N) 이하의 알고리즘을 요구하는 것이라 추측할 수 있겠습니다. 그리고 보통 로그가 붙은 건 정렬성을 이용하는 경우가 많죠. 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
suhee
먼저 문제 링크입니다.
ANNIETIBBER
저는 annie/tibber의 좌표와 두 별의 좌표를 직선으로 연결하였을때 기울기 값을 계산하여 비교하는 방법을 이용했습니다.
annie와 tibber의 좌표에서 두 별에 대한 각각의 기울기를 구한 후,
기울기 값을 비교했을때 부등호 방향이 다르게 나오면 count++ 하는 방식으로요.
하지만 제 풀이법으로는 시간초과가 나오네요..
어떤 방식으로 문제를 풀어야 하는지 힌트를 얻고싶습니다.
9년 전