p_ce1052   3년 전

풀이글을 보면 시간복잡도가 세제곱이라고 되어있던데 2*n개의 가로줄과 2*n개의 세로줄에서 사각형을 하나 뽑아내면 대략(2nC2)^2 = 대략 n^4에 입력으로 들어온 사각형 중 하나에 포함되는지 확인하려면 n번 비교해야하니 최종적으로 n^5이 아닌가요? 어떻게 세제곱이 나오나요?

yj10516   3년 전

모든 2nC2 조합을 확인 할 필요는 없고 가로줄과 세로줄을 정렬한 후

모든 연속된 두개의 가로줄과 연속된 두개의 새로줄로 만든 직사각형이

원래 직사각형에 포함하는지 확인하면 될 것 같습니다.

p_ce1052   3년 전

아아...가장 작게 짜른 애들만 확인해도 다 확인되는군요 감사합니다

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