이 문제의 시간이 500ms 이기 때문에 탐색 문제가 아닌 수학 문제라고 판단하였습니다. 그리고 규칙성을 찾아보기 위해 노력하였는데, 전문적인 수학 지식을 요하는지(아니면 제가 멍청한지) 규칙은 찾을 수 없더군요...
먼저 '도형의 넓이', '모든 경우의 삼각형 넓이의 합', '모든 f(i)의 합' 을 구하여 정답은 나올 수 있었습니다.
그리고 (당연하지만) 모든 f(i)의 합 = (모든 경우의 삼각형 넓이의 합) - (점 i를 포함하는 모든 삼각형의 합) 이라는 식은 찾을 수 있었습니다.
그런데 전탐색 없이 '모든 경우의 삼각형 넓이의 합' 과 '점 i를 포함하는 모든 삼각형의 합'을 구할 방법을 모르겠더군요. 그런데 그냥 쓸 경우 nC3 의 경우라 시간복잡도가 O(n^3) 입니다...
부디 어떤 방법으로(어떤 수식으로) 이 문제를 해결할 수 있을지 힌트라도 주시면 감사하겠습니다.
8년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
luku756
GEOMETRY 문제를 푸는 중 도저히 해결하지 못해 질문 올립니다.
이 문제의 시간이 500ms 이기 때문에 탐색 문제가 아닌 수학 문제라고 판단하였습니다. 그리고 규칙성을 찾아보기 위해 노력하였는데, 전문적인 수학 지식을 요하는지(아니면 제가 멍청한지) 규칙은 찾을 수 없더군요...
먼저 '도형의 넓이', '모든 경우의 삼각형 넓이의 합', '모든 f(i)의 합' 을 구하여 정답은 나올 수 있었습니다.
그리고 (당연하지만) 모든 f(i)의 합 = (모든 경우의 삼각형 넓이의 합) - (점 i를 포함하는 모든 삼각형의 합) 이라는 식은 찾을 수 있었습니다.
그런데 전탐색 없이 '모든 경우의 삼각형 넓이의 합' 과 '점 i를 포함하는 모든 삼각형의 합'을 구할 방법을 모르겠더군요. 그런데 그냥 쓸 경우 nC3 의 경우라 시간복잡도가 O(n^3) 입니다...
부디 어떤 방법으로(어떤 수식으로) 이 문제를 해결할 수 있을지 힌트라도 주시면 감사하겠습니다.
8년 전