지문이 짧길래 저번에 카페에서 떠들다가 핸드폰 메모장을 이용해서 대충 풀이를 내봤는데 흥미로웠다.어제 메모장 정리하다 메모를 발견해서 구현해보았다. 일단 문제 자체가 너무 점화식으로 잘 표현될 수 있을 거라는 느낌을 풍긴다.이 문제의 어려움은 $n+1$개의 직사각형 중 $n$개는 정확히 계단 모서리에 하나씩 걸치지만 딱 한 개의 직사각형은 중앙 어디에든 위치할 수 있다는 점에 있다. 따라서 중앙 어디에든 위치할 수 있는 직사각형의 위치를 고정시킨다면 문제가 수월해질 것이다. 고정했다고 생각하고 문제를 바라보면, 직사각형의 두 변을 연장해서 가능한 답의 꼴들을 찾아볼 수 있다.무조건 두 변 중에 한 변의 연장선은 어떤 조각도 가로지르지 않는다는 관찰이 핵심적이다. 이를 이용하여 약간의 포함배제를 적용하면 ..