3개의 댓글이 있습니다.
-
-
Being -
제가 답변을 드려야 좋을 것 같네요. 예상하셨듯, 이 문제의 경우 모든 경우를 시도하는 것보다 좋은 방법이 여러 가지가 있습니다. 50ms대까지 내려가는 데에는 그냥 실수 연산 대신 유리수를 생각해서 계산하면 되지만, 그 밑으로 내려가려면 시간복잡도가 다른 알고리즘을 사용해야 하죠.
그 중 가장 직관적이면서 쉬운 발견을 하나 알려드릴게요. 만약 길이가 2L보다 긴 구간이 있다고 가정해 봅시다. 그러면 우리는 이 구간을 반드시 올바른 두 개의 구간으로 쪼갤 수 있지요? 각각의 구간의 평균을 a/b와 c/d라 하면, 둘 사이에는 대소관계가 존재할 거구요. 고등학교때 가비의 리.. 라고 하던 아래의 공식이 성립함을 생각할 수 있습니다: \frac{a}{b} \le \frac{a+c}{b+d} \le \frac{c}{d}
무슨 말인고 하니, 길이가 2L인 구간을 쪼개면 둘 중 한 구간은 반드시 전체 평균보다 크거나 같게 된다는 뜻입니다. 즉, 길이가 2L 이상인 구간은 고려할 필요가 없다는 결론이 나오지요.가장 빠른 풀이인 O(N) 알고리즘도 이 관찰을 토대로 한 것입니다.
그리고, 질문하실 때 자세하게 내용을 적으셔도 상관없습니다. :) 걱정되시면 <spoiler> </spoiler> 안에 감싸시면 위처럼 보입니다.
10년 전 link
-
-
-
EugeneChung -
덕분에 의문이 풀렸습니다. 새벽에 짜서 올렸더니 25ms까지 줄였네요. 아직 optimize 가능한 부분이 있어서 한번 더 올려볼 생각입니다.
다른 분들을 위해서 제가 이 문제를 통해서 배운 것들을 정리해 봅니다.
입력값으로 준비 작업이 필요한 경우, 입력을 읽는 루프에서 함께 처리한다.
나눗셈을 해서 크기 비교를 해야 하는 경우, 매번 나누지 말고 분모와 분자를 따로 관리하면서 곱셈으로 비교한다.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
EugeneChung
학창 시절에 수학 공부를 좀더 열심히 해둘 걸 하는 생각이 드는 요즘입니다.
FESTIVAL 문제를 풀긴 했지만 144ms가 걸렸습니다. 3ms~15ms의 정답이 있는 걸 보고 분명히 loop를 더 많이 도는 상황이라고 생각이 들더군요.
빠른 코드들을 보니까 기본적인 의도 자체는 제가 생각한 것과 비슷한데 complete search를 하지 않아서 loop를 훨씬 적게 돈다는 걸 알게 되었습니다.
입력값이 1000 1 이면 제 코드는 1000+ .... + 1 해서 약 50만번을 돌고, 빠른 코드들은 1000번만 돕니다. 1000 2 인 경우는 500+167... 어떤 조건문으로 loop를 도는지는 이해가 됐는데 왜 모든 경우의 수를 안 해봐도 되는지 이해가 안 갑니다.
여기다 너무 자세한 내용을 적으면 안 될 것 같아서 좀 두리뭉술하게 적었습니다. 그래도 빠른 정답 코드를 작성하신 분들은 제가 무슨 얘기를 하는지 이해하실 거라고 생각이 듭니다.
10년 전