leekt321   6년 전

정보를 찾아봐도 구하기가 힘드네요.

힌트 주실수 있는 분 적어주시면 감사하겠습니다.

jh05013   6년 전

위쪽 변이 아래쪽 변보다 짧은 사다리꼴의 개수를 셉니다. 나머지 경우는 같은 방법으로 구할 수 있습니다.

가능한 사각형을 일일히 보는 방법은 O(N4) 시간이 걸립니다. 여기서 하나의 전처리를 하면 "위쪽 밧줄에서 말뚝 2개를 이미 골랐을 때 가능한 사다리꼴의 개수"를 O(1)만에 구할 수 있고, 이러면 O(N2) 시간이 걸립니다. 하나의 전처리를 더 하면 시간 내에 돌아가는 알고리즘을 얻습니다.

leekt321   6년 전

감사합니다 생각했었던 내용과 비슷했는데, dp배열 정의가 조금 달랐네요

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