현재 정사각형의 한 경계 행과 한 경계 열을 골라 합치면 길이가 한 변의 길이보다 1 작은 L 타일이 된다. 목표 칸이 위쪽 경계 행에 없다면 위쪽을, 있으면 아래쪽을 고른다. 열도 같은 방법으로 고른다. 한 변이 2 이상이면 선택한 행과 열 모두 목표 칸을 피한다. 이 L을 채우면 목표를 포함하는 한 변이 1 작은 정사각형이 남는다. 이를 반복하면 길이 부터 1까지 정확히 한 번씩 사용하고 마지막에 목표 칸만 남는다. 따라서 항상 가능하다. 시간과 공간은 이다. 서브태스크 1은 큰 타일부터 가능한 중심과 네 회전을 모두 시도하는 백트래킹으로 해결할 수 있다. 느슨한 시간 상한은 이며 에서 충분하다. 출력값은 최대 999, 한 케이스 칸 수는 최대 이며 모든 값은 64비트 범위 안이다.
Solution written by GPT6.1
