codeground : Rectangles [SCPC 2016 - 2차 예선]

Rectangles [SCPC 2016 - 2차 예선]

https://www.codeground.org/practice/practiceProbView.do?probId=30

문제는 저 점 (7, 3.5)를 찾는 것이다.

R1은 R3을 포함하고, R3는 R4를 포함한다. 그리고 R1,R3,R4는 서로 겹치지 않는다. 점 (7, 3.5)는 겹치지 않고 서로 포함관계에 있는 3개의 Rectangle 안에 포함되고, 위와같은 조건을 만족하면서 더 많은 Rectangle 안에 포함되는 점을 찾을 수 없으므로 답은 3을 출력하면 된다.

그렇다면 답은 어떻게 구할 수 있을까?

먼저 R1에 포함되는 최대 집함을 찾아보자.

Ri의 집합의 크기를 Si라 두면,

R1은 R2,R3,R4를 포함하므로 S1 = max(S2,S3,S4) + 1이다.

마찬가지로 R2,R3,R4를 각각 써보면

S2 = 1

S3 = S4 + 1

S4 = 1

S5 = 1

재귀와 메모이제이션을 이용하면 S1 = 3, S2 = 1, S3 = 2, S4 =1, S5 = 1이라는 메모이제이션 결과를 찾을 수 있고, 이중 가장 큰 값인 3을 결과로 출력하면 된다.

이 알고리즘 시간복잡도는 N^2으로 text case에서 N <= 5000이므로 아슬아슬하게 통과할 수 있다. 하지만 실제 시간은 적게 걸리는 것으로 봐서 데이터가 작은 듯..