[platinum3][해설안봄, 분류확인] 10803 정사각형 만들기

https://www.acmicpc.net/problem/10803

13361 다이아5 문제를 도전하다가 구현이 너무 빡세 보여서 반포기 상태에 이른 후, 멘탈 재정비의 시간을 가지고 다시 문제를 풀기 시작했다.

  이 문제는 구현은 쉬웠으나, 왜 그런지 증명이 어려운 문제였다.

정사각형의 두변의 길이가 적당히 작을 땐 정사각형을 세로 or가로로 쪼개서 재귀로 dp를 구현하면 된다.

그러나 길이가 길때는 O(n^2)이므로 시간초과가 될 것이다.

그렇다면 어떻게 해아할까?

생각해보면 직감적으로, n = 100, m = 10000 처럼 m이 매우 길 경우를 생각해보자.

 변이 100인 정사각형이 조각중에 반드시 포함될 것 같지 않은가?'

증명하긴 힘들지만, 한 변이 매우 길어질 경우 작은변을 한 변으로 하는 정사각형이 포함될 것 같은 직감이 강하게 든다.

한변의 길이가 매우 길때, 다른 변의길이 정사각형으로 채우는게 압도적으로 빨리 채울 수 있기 때문이다.

 

위와 같은 경우, 변 5인 정사각형이 몇개가 될진 모르겠지만 반드시 포함될 것 같다.

정사각형으로 채우고 남은 변의 길이는 2 or 7 or 12 or 17 ... 등이 될 것이다.

 

 

두변의 길이가 차이가 별로 안날 때는 이를 테면 5, 7 인 경우에는  길이5의 정사각형을 포함시키는 게 맞을지 확실치 않다.

위와 같은 경우가 있을 수도 있기 때문이다.

 

그렇다면 두변의 길이차이가 작을 때는 재귀 dp를 이용해  세로 , 가로를 쪼개며 확인해 볼 수 있다.

n1 <= 100, n2 <= 10000가 제한조건인 이유가 여기 있었다.  작은변의 최대값은 100이므로 O(n^2)으로 충분히 계산이 가능하다.

 

 

요약하자면 정사각형으로 충분히 채운후, 적당량 남았을 때 재귀dp를 사용하면 된다.

 

두변의 길이차이가 얼마까지 줄어들어야 재귀 dp를 사용할 수 있을 까?

 

우선 처음엔 작은변 * 2, 즉 위의 경우   가로가 14이하 일때 재귀dp를 사용하게 하였다. 그랬더니 실패.

이번엔 작은변 * 3 이하일 때 dp를 사용했더니 통과하였다.