Codeforces Round 866 (Div. 2) D. The Butcher

Problem - D - Codeforces

세로 x 가로 y 인 사각형으로부터 잘려 나온 n개의 조각들이 있다고 가정하자.

 

(1)

n개의 조각들로 세로 x 가로 y 인 사각형을 만들 수 있는지 판단할 수 있다.

 

(2)

첫 번째 조각은 세로가 x이거나 가로가 y인 사각형 이어야 한다.

세로가 x인 조각과 가로가 y인 조각은 동시에 존재할 수 없다.

세로가 x인 조각을 먼저 잘랐다고 가정하면 가로는 y보다 작아지므로 가로가 y인 조각을 영원히 사용할 수 없다.

가로가 y인 조각을 먼저 잘랐다고 가정하면 세로는 x보다 작아지므로 세로가 x인 조각을 영원히 사용할 수 없다.

따라서 동시에 존재할 수 없으므로 항상 다음에 사용할 조각의 가로 또는 세로의 길이는 유일하다.

 

만약 가로가 y인 조각으로 정해졌다고 가정하자. 세로가 다른 가로가 y인 조각이 여러 개 존재할 수 있다. 이들의 시퀀스는 어떤 시퀀스든 상관이 없다. (2)에 의해서 항상 가로가 y인 조각이 있는 한 그 조각밖에 선택할 수밖에 없고 결국 어떤 시퀀스를 선택하든 가로가 y인 조각의 세로의 합은 항상 같기 때문이다.

 

따라서 자를 수 있는 길은 유일하므로 잘라 보고 조각이 남으면 불가능, 안 남으면 가능하다.

 

문제에선 세로 x, 가로 y가 정해지지 않았다. 따라서 이제 가능성 있는 x와 y를 정해주기만 하면 된다.

 

처음 조각과 처음 자른 방향을 안다면 처음 사각형의 크기를 알 수 있다.

처음 조각이 정해졌고 가로 방향으로 잘랐다면 전체 사각형의 크기는 가로는 처음 조각과 같고 세로는 전체크기 / 가로.

처음 조각이 정해졌고 세로 방향으로 잘랐다면 전체 사각형의 크기는 세로는 처음 조각과 같고 가로는 전체크기 / 세로.

 

처음에 가로로 잘랐다면 처음 조각의 가로는 최대가 되어야 한다. 왜냐하면 전체 조각의 크기가 처음 조각의 가로가 되기 때문이다. 세로도 마찬가지이다.

 

따라서 가로로 잘랐을 때는 처음 조각을 가로가 최대인 조각 아무거나 하나 선택하면 되고 세로로 잘랐을 때는 처음 조각을 세로가 최대인 조각 아무거나 하나 선택하면 된다. 그렇게 해서 전체 가로와 세로가 정해졌다면 (1)에 의하여 두 경우가 각 각 옳은지 판단하면 된다.