가장 나이브하게 풀면 O(R^3C^3) 정도의 해법을 생각해 볼 수 있겠다. 여기서 어떤 사각형 안에 빈 자리 개수 합을 미리 계산 해 놓으면 (동적 계획법으로 할 수 있다) O(R^2C^2) 로 줄일 수 있다. 그래도 시간 초과를 면하기는 힘들다.여기서 (r1, c1) 이 어떤 직사각형의 맨 왼쪽 하단, (r2,c2)를 직사각형의 맨 오른쪽 상단이라고 해보자. 그리고 이 직사각형의 빈 좌석 개수를 K라고 하자.
또 다른 직사각형의 맨 왼쪽 하단을 (r1,c1)이라고 하고 맨 오른쪽 상단을 (r2+1, c2)이라고 하자. 그리고 이 직사각형의 빈 좌석 개수를 K’이라고 하자.
그러면 당연히 K’<=K가 된다. 그 말은 4중 루프에서 세 번째, 네 번째 루프를 하나로 만들 수 있다는 뜻이다. 그래서 이 문제를 O(R^2C) 정도의 시간 복잡도로 풀 수 있다.
영어로 이와 같은 테크닉을 Sliding Window Technique 이라고 불린다. 이와 관련된 문제는 대회에서 종종 나오는 듯 하니 몇 개 풀어보길 바란다. 더블릿에도 몇 개 있다. (예: KOI 2011 중등부 3)
출처:likepad