문제 링크
- http://icpc.me/8131
문제 출처
- 2005/2006 POI Stage2 6번
사용 알고리즘
- 슬라이딩 윈도우
시간복잡도
- O(NM)
풀이
열심히 직사각형을 깎아내다보면, 마지막에는 가로 혹은 세로 길이가 1인 직사각형을 없애게 됩니다. 마지막에 없애는 직사각형의 크기를 1×K 또는 K×1이라고 하면, 직사각형을 총 (N−1)+(M−K) 또는 (N−K)+(N−1)번 없애게 됩니다. (N+M)은 일정하므로 K를 최대화시키는 것이 이 문제의 목적입니다.
마지막에 가로로 길쭉한 직사각형을 하나 남겨놓는다고 합시다. 세로로 길쭉한 직사각형을 남기는 것이 최적인 경우에는 배열을 회전시켜서 한 번 더 해주면 됩니다.
마지막까지 남겨놓을 가로로 길쭉한 직사각형의 양쪽 끝 지점을 고정해주면, 그런 직사각형을 남겨놓을 수 있는지 O(N+M)에 판별할 수 있습니다. 총 O(M2)가지의 경우가 있으므로 O(M2(N+M))정도에 문제를 풀 수 있지만 N과 M이 너무 큽니다.
하지만 투포인터 느낌으로 끝 지점을 관리해주면 총 O(M)개의 경우만 봐주면 되고, O(M(N+M))에 해결할 수 있습니다.
배열을 회전시키고 이 작업을 한 번 더 해주면 O(N2+M2) 정도 시간에 문제를 풀 수 있습니다.
전체 코드
1 |
|